Submission #545740

#	Time	Username	Problem	Language	Result	Execution time	Memory
545740		pure_mem	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	217 ms	23008 KiB

bulves

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define X first
#define Y second
#define MP make_pair

using namespace std;

const int N = 5e5 + 1;
const ll INF = 1e12 + 1;

int n;
ll a[N], b[N], dif[N];

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for(int i = 1;i <= n;i++)
 		cin >> a[i] >> b[i], dif[i] = dif[i - 1] + a[i] - b[i];

   	ll ans = 0;
   	priority_queue<ll> dp;

 	for(int i = 1;i <= n;i++) {
 		ans += abs(dif[i]);
 		if(dif[i] < 0)
 			dif[i] = 0;	

 		dp.push(dif[i]);
 		dp.push(dif[i]);
 		dp.pop();	
 	}

 	for(;!dp.empty();) {
 	//	cerr << dp.top() << " " << dif[n] << "\n"; 
 		ans -= min(dp.top(), dif[n]);
 		dp.pop();
 	}

	cout << ans;
}

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