Submission #253411

#	Time	Username	Problem	Language	Result	Execution time	Memory
253411		vioalbert	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	202 ms	19304 KiB

bulves

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

const ll N = 5e5+5, MAX = 3e4+5, ZERO = 3e4, INF = 1e18;
ll n, delta;
ll val[N], pref[N];

void read() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		ll a, b; cin >> a >> b;
		val[i] = a - b;
	}
}

void solve() {
	pref[0] = 0;
	for(int i = 1; i <= n; i++) {
		pref[i] = pref[i-1] + val[i];
	}
	delta = pref[n];

	ll ans = 0, x;
	priority_queue<ll> pq;
	pq.push(0);
	for(int i = 1; i <= n; i++) {
		x = pref[i];
		if(x < 0) {
			ans += -x;
			x = 0;
		} else if(x > delta) {
			ans += x - delta;
			x = delta;
		}
		pq.push(x);
		pq.push(x);
		ans += pq.top() - x;
		pq.pop();
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read();
	solve();
	return 0;
}

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