Submission #491548

#	Time	Username	Problem	Language	Result	Execution time	Memory
491548		phamhoanghiep	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	197 ms	19144 KiB

bulves

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
typedef long long ll;
int a[maxn];
int b[maxn];
ll d[maxn];
int n;
ll ans=0; // dp[n][0]
// dp[n][i]: excessive of at most i
priority_queue<ll> pq;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1 ; i<=n ; i++) {
        cin>>a[i]>>b[i];
        d[i]=d[i-1]+1ll*(a[i]-b[i]);
        //cout<<"d "<<i<<" = "<<d[i]<<endl;
    }
    for(int i=1 ; i<n ; i++) {
        ans+=abs(d[i]);
        if(d[i]<0) d[i]=0;
        pq.push(d[i]);
        if(pq.top()>d[i]) {
            pq.pop();
            pq.push(d[i]);
        }
        //cout<<"ans = "<<ans<<endl;
        // slope change point 
    }
    while(!pq.empty()) {
        ans-=min(pq.top(),d[n]);
        pq.pop();
    }
    cout<<ans;
}

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