Submission #1362245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362245		Newtonabc	Potatoes and fertilizers (LMIO19_bulves)	C++20	100 / 100	193 ms	16332 KiB

bulves

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+10;
ll a[N],b[N],d[N];
int main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i] >>b[i];
    ll s=0,ret=0;
    priority_queue<ll> q;
    for(int i=1;i<=n;i++) d[i]=d[i-1]+a[i]-b[i];
    for(int i=1;i<=n;i++){
        //cout<<d[i] <<" ";
        if(d[i]<0){
            ret+=-d[i];
            q.push(0),q.push(0);
            ret+=q.top();
        }
        else if(d[i]>d[n]){
            ret+=d[i]-d[n];
            q.push(d[n]),q.push(d[n]);
            ret+=q.top()-d[n];
        }
        else{
            q.push(d[i]),q.push(d[i]);
            ret+=q.top()-d[i];
        }
        q.pop();
    }
    cout<<ret;
}

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