Problem Info
USACO 2013 November Contest, Bronze
Problem 2. Goldilocks and the N Cows
http://www.usaco.org/index.php?page=viewproblem2&cpid=341
My Work
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <tuple>
#include <numeric>
#include <climits>
#include <fstream>
using namespace std;
typedef long long ll;
#define endl "\n"
#define cout fout
#define cin fin
bool comp(pair<ll, bool> e, pair<ll, bool> f) {
if (e.first == f.first) {
return e.second;
}
return e.first < f.first;
}
void solve()
{
ifstream fin ("milktemp.in");
ofstream fout ("milktemp.out");
ll n, x, y, z;
cin >> n >> x >> y >> z;
vector <pair<ll, bool>> points;
for (ll i = 0; i < n; i++) {
ll a, b;
cin >> a >> b;
points.push_back({a, true});
points.push_back({b, false});
}
sort(points.begin(), points.end(), comp);
ll prev = 0;
ll cur = 0;
ll ans = -1;
for (ll i = 0; i < points.size(); i++) {
ll temp = 0;
if (points[i].second) {
cur++;
ll after = n - prev - cur;
temp = (x * prev) + (y * cur) + (z * after);
ans = max(ans, temp);
} else {
ll after = n - prev - cur;
temp = (x * prev) + (y * cur) + (z * after);
ans = max(ans, temp);
cur--;
prev++;
}
}
cout << ans << endl;
return;
}
int main()
{
ll t = 1;
while (t--) {
solve();
}
}
I downloaded the test data and got the same output as the official output for test case 2. But the USACO grading server marked it as incorrect.