Problem Info
Closest Cow Wins
http://www.usaco.org/index.php?page=viewproblem2&cpid=1158
My Work
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
using namespace std;
long long K, M, N;
vector<pair<long long, long long>> patches;
vector<long long> nhoj;
int main()
{
// Input
cin >> K >> M >> N;
long long t1, t2;
for (int i = 0; i < K; i++) {
cin >> t1 >> t2;
patches.push_back({ t1, t2 });
}
for (int i = 0; i < M; i++) {
cin >> t1;
nhoj.push_back(t1);
}
// Make sure the data is sorted
sort(patches.begin(), patches.end(),
[](pair<long long, long long> a, pair<long long, long long> b) {
return a.first < b.first;
});
sort(nhoj.begin(), nhoj.end());
vector<long long> answers; // The amounts of tastiness we can get by adding a single cow
// Get the tastiness before the first cow of Farmer Nhoj
int idx = 0;
long long before = 0;
while (patches.at(idx).first < nhoj.front()) {
before += patches.at(idx).second;
idx++;
}
answers.push_back(before);
// Get the maximum tastiness between each set of two of Farmer Nhoj's cows
// We calculate the maximum we can get from just placing one cow, and also the total (for when we want to place two cows)
for (int i = 0; i < nhoj.size() - 1; i++) {
long long oneCow = 0; // Max tastiness we can get if we only place one cow in this region
int start = nhoj.at(i);
int end = nhoj.at(i + 1);
int range = (end - start) / 2; // Range of patches when we palce one cow
int idx2 = idx;
long long currWindow = 0; // Local value for oneCow with current "idx" var
long long total = 0; // Total patch tastiness in this region
while (idx < patches.size() && patches.at(idx).first < end) {
if (patches.at(idx).first == start) continue; // Make sure we don't count one that a Nhoj cow is already sitting on with since we can never get those patches
total += patches.at(idx).second;
while (idx2 < patches.size() && patches.at(idx2).first < patches.at(idx).first + range && idx2 < end) {
currWindow += patches.at(idx2).second;
idx2++;
}
oneCow = max(oneCow, currWindow);
currWindow -= patches.at(idx).second;
idx++;
}
answers.push_back(oneCow); // Push the max tastiness we can get with one cow
answers.push_back(total - oneCow); // Push how much tastiness we would add if we put in two cows instead of one
}
// Get tastiness after last Nhoj cow
int indexThingy = patches.size() - 1;
long long after = 0;
while (patches.at(indexThingy).first > nhoj.back()) {
after += patches.at(indexThingy).second;
indexThingy--;
}
answers.push_back(after);
// Sort answers and do output
sort(answers.begin(), answers.end(), greater<long long>());
long long ans = 0;
for (int i = 0; i < N; i++) {
ans += answers.at(i);
}
cout << ans << "\n";
return 0;
}
Sorry if my explanation is a little wacky. Basically, my code goes through each “bubble” between two of Nhoj’s cows. If we place two cows in each region, it is guaranteed that we can get all the patches within that bubble. If we only place one, we’ll only get part of it. My code goes through each bubble (as well as before the first Nhoj cow and after the last one) and calculates the total possible tastiness if we use two cows, as well as the max tastiness if we only use one. It pushes the amount of tastiness can be added by a cow in different locations to a vector, sorts it, adds together the first N elements, and outputs the answer.
What I’ve Tried
I’ve tried downloading the test data but it’s huge so I don’t know what’s really wrong with my code. I also tried changing the sample case input but my code behaves as expected every time.
Question
I only pass the sample case, everything else is wrong. Can someone please explain what I’m doing wrong? I know I probably did something dumb but this is like my third attempt at implementing this and I’ve spent an embarrassingly long time on this and I’m honestly exhausted at this point. Any help is appreciated.
Checklist
See How to ask for help on a problem for more information.
- Include a link to the problem
- Format your post (especially code blocks)
- Include what you’ve tried so far
- Add comments to your code
- Read the debugging module