Submission #697959

#	Time	Username	Problem	Language	Result	Execution time	Memory
697959		siewjh	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	139 ms	15312 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums; cin >> nums;
	priority_queue<ll> pq;
	vector<ll> pref(nums + 1);
	pref[0] = 0;
	for (int i = 1; i <= nums; i++){
		ll s, d; cin >> s >> d;
		pref[i] = pref[i - 1] + s - d;
	}
	ll ans = 0;
	for (int i = 1; i <= nums; i++){
		if (pref[i] < 0) {
			ans -= pref[i];
			pref[i] = 0;
		}
		else if (pref[i] > pref[nums]){
			ans += pref[i] - pref[nums];
			pref[i] = pref[nums];
		}
		pq.push(pref[i]);
		pq.push(pref[i]);
		ans += pq.top() - pref[i];
		pq.pop();
	}
	cout << ans;
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36