Submission #744492

#	Time	Username	Problem	Language	Result	Execution time	Memory
744492		Szymon_25	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	422 ms	15192 KiB

bulves

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;

ll f = 0;         
priority_queue<ll> Q;  //punkty przegiecia DP

int main() {
	cin >> n;
	
	vector<ll> pref(n+1);
	
	for (int i=1; i<=n; i++) {
		int a, b;
		cin >> a >> b;
		pref[i] = a - b + pref[i - 1];
	}
	
	for (int i=1; i<n; i++){
		if(pref[i] < 0){
			f -= pref[i]; 
			pref[i] = 0;
		}
		f += pref[i];
		Q.push(pref[i]);
		Q.push(pref[i]);
		Q.pop();
	}

	while (Q.size()) {
		ll tmp = Q.top();
		Q.pop();
		f -= min(tmp, pref[n]);
	}

	cout << f << "\n";
}

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