# USACO 2016 February Contest, Bronze Problem 3. Load Balancing

Hi. My code for this problem passes all test cases except for #7 (Run time or memory limit exeeded). However, test case 10 has much bigger data (n=100, b=1000000) than test case 7 (n=100, b=5000) and my code passed. Why is this happening? I’d appreciate any help here.

``````#include <bits/stdc++.h>
using namespace std;
int WIDTH, HEIGHT;
int TopLeft(int a, int b, vector<vector<bool>> matrix)
{
int NumberOfCows = 0;
for (int i = 0; i < b; i++)
for (int j = 0; j < a; j++)
NumberOfCows += matrix[i][j];

return NumberOfCows;
}
int TopRight(int a, int b, vector<vector<bool>> matrix)
{
int NumberOfCows = 0;
for (int i = 0; i < b; i++)
for (int j = a; j < WIDTH; j++)
NumberOfCows += matrix[i][j];

return NumberOfCows;
}
int BottomLeft(int a, int b, vector<vector<bool>> matrix)
{
int NumberOfCows = 0;
for (int i = b; i < HEIGHT; i++)
for (int j = 0; j < a; j++)
NumberOfCows += matrix[i][j];

return NumberOfCows;
}
int BottomRight(int a, int b, vector<vector<bool>> matrix)
{
int NumberOfCows = 0;
for (int i = b; i < HEIGHT; i++)
for (int j = a; j < WIDTH; j++)
NumberOfCows += matrix[i][j];

return NumberOfCows;
}
int main()
{
freopen("balancing.in","r",stdin);
freopen("balancing.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, b;
cin >> n >> b;
vector<pair<int, int>> cows(n);
for (int i = 0; i < n; i++)
cin >> cows[i].first >> cows[i].second;

// find width & height of the matrix
set<int> distinct_x_values;
set<int> distinct_y_values;
for (int i = 0; i < n; i++)
{
distinct_x_values.insert(cows[i].first);
distinct_y_values.insert(cows[i].second);
}
WIDTH = distinct_x_values.size();
HEIGHT = distinct_y_values.size();

// create matrix
vector<vector<bool>> matrix(HEIGHT, vector<bool>(WIDTH, false));
for (int i = 0; i < n; i++)
{
int x_values_left = 0;
int y_values_up = 0;
for (auto x : distinct_x_values)
{
if (x < cows[i].first)
++x_values_left;
else
break;
}
for (auto y : distinct_y_values)
{
if (y > cows[i].second)
++y_values_up;
}
matrix[y_values_up][x_values_left] = true;
}

// go through all possible pairs of (a, b)
int ans = 1e9;
for (int i = 1; i < HEIGHT; i++)
for (int j = 1; j < WIDTH; j++)
ans = min(ans, (max(TopLeft(i, j, matrix), (max(TopRight(i, j, matrix), (max(BottomLeft(i, j, matrix), BottomRight(i, j, matrix))))))));

cout << ans;
return 0;
}
``````