Submission #418611

#	Time	Username	Problem	Language	Result	Execution time	Memory
418611		Blagojce	Potatoes and fertilizers (LMIO19_bulves)	C++11	100 / 100	172 ms	13248 KiB

bulves

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 5e5+5;

int n;
ll d[mxn];

void solve(){
	cin >> n;
	fr(i, 1, n+1){
		int a, b;
		cin >> a >> b;
		d[i] = d[i-1] + a - b;
	}
	
	pq<int> Q;
	
	ll ans = 0;
	fr(i, 1, n+1){
		int vinrange = min(max(d[i], 0LL), d[n]);
		Q.push(vinrange);
		if(Q.top() > d[i]){
			Q.push(vinrange);
			ans += Q.top()-d[i];
			Q.pop();
		}
		else if(d[i] > d[n]){
			ans += d[i]-d[n];
		}
	}
	cout<<ans<<endl;
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}	

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