USACO Gold 2016 Open - Splitting the Field

Authors: Óscar Garries, Benjamin Qi, Ryan Chou

Table of Contents


Official Analysis (Java)

Warning: Weak Test Data

Some accepted submissions may give different outputs on the following test case:

The right answer should be 66.

Code Snippet: Test Case (Click to expand)


Since the enclosures must be rectangular, there must be a vertical or horizontal line that separates the two. Otherwise, we'd have a case where one enclosure would have to overlap the other in order to enclose all the cows.


Thus, we'll perform two sweeps, one checking vertical splits, and the other checking horizontal splits. To keep track of the best answer, we'll keep prefix and suffix minimums and maximums to calculate each possible solution in O(1)\mathcal{O}(1) time.

We can also use a binary search tree instead of prefix/suffix minimums and maximums. To do this, we can create two ordered sets: a set representing the current enclosure, and a set representing the other enclosure. As we sweep across these coordinates, we'll add them to the current set and remove them from the other enclosure. To query, we'll fetch the minimum and maximum values from the sets.


Time Complexity: O(NlogN)\mathcal{O}(N \log N)


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
ll ans = 0;
vector<pair<int, int>> cows;
/** returns the maximum area saved by testing splits along cows[i].first */


import java.util.*;
public class SplittingTheField {
// returns updated min/maxs when considering a new coordinate
public static Pair upd(Pair a, long b) {
return new Pair(Math.min(a.first, b), Math.max(a.second, b));
public static void main(String[] args) throws Exception {


with open("") as read:
n = int(read.readline())
cows = [list(map(int, read.readline().split())) for _ in range(n)]
ans = 0
def search():
returns the maximum area saved by testing splits along cows[i].first

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!