December 2021 Silver Closest Cow Wins

Problems and Contests
#1

tl;dr

I’m currently solving this problem, but for some reason I’m only getting 15/21 test cases. I tried implementing the solution that the editorial had, but I saw a flaw in that solution: what happens when you add twoCows - oneCows to your answer but oneCows isn’t added?

Here is my code:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;

#define forn(i, n) for(ll i = 0; i < n; i++)
#define pb push_back
#define f first
#define s second
#define sor(x) sort(begin(x), end(x))
#define rsor(x) sort(begin(x), end(x), greater<ll>())

int main(){
	ll k, m, n; cin >> k >> m >> n;
	vpl locations; vl res;
	forn(i, k){
		ll p, t; cin >> p >> t;
		locations.pb({p, t});
	}
	forn(i, m){
		ll f; cin >> f;
		locations.pb({f, -1});
	}
	sor(locations);
	ll twoCow = 0, lst = -1;
	forn(i, k + m){
		if(locations[i].s != -1){
			twoCow += locations[i].s;
		} else {
			if(lst == -1){
				res.pb(twoCow);
			} else {
				ll oneCow = 0, curSum = 0;
				ll l = lst + 1, r = lst + 1;
				while(r <= i){
					if(locations[r].s == -1){
						break;
					} else {
						ll dist1 = (locations[r].f - locations[l].f);
						ll dist2 = (locations[r].f - locations[lst].f);
						ll dist3 = (locations[i].f - locations[r].f);
						if(dist1 <= dist2 && dist1 <= dist3){
							curSum += locations[r].s;
							r++;
						} else {
							oneCow = max(oneCow, curSum);
							curSum -= locations[l].s;
							l++;
						}
					}
				}
				res.pb(oneCow);
				res.pb(twoCow - oneCow);
			}
			lst = i;
			twoCow = 0;
		}
	}
	res.pb(twoCow);
	rsor(res); ll ans = 0;
	forn(i, n){
		ans += res[i];
	}
	cout << ans << endl;
}

The only thing I did differently here is that I used two-pointers instead of sliding window. Could this potentially be the issue in my code?

Please let me know! TIA.

#2

Please follow the directions (try stress testing?): How to ask for help on a problem - #2

This is addressed in the analysis …

I would say that the analysis solution maintains two pointers to the endpoints of a sliding window. In that sense it involves both sliding window and (not instead of) two pointers. You’re right that you’re not doing the same thing as the analysis though (which is why you’re getting WA …)

#3

Why is my version wrong? Can you provide a simple test case for me to think about?

#4

I’m pretty sure oneCows is always bigger or equal to twoCows - oneCows because the sliding window is half the length of the distance between Nhoj’s cow’s location. It wouldn’t make sense if twoCows - oneCows were to be bigger than oneCows because it will always be the maximum. Try drawing this or thinking about it and you will see that oneCows will always be equal to or bigger than twoCows - oneCows. If you find a case where twoCows - oneCows is bigger than oneCows, please post the case.