Submission #489682

#	Time	Username	Problem	Language	Result	Execution time	Memory
489682		andrii	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	131 ms	15208 KiB

bulves

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pll pair<ll, ll>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> yree;
const ld inf = 0x3fff3fff3fff3fff;
const ll N = 5e5+18;

ll a[N];

signed main(){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
    ll n;
    cin >> n;
    for(ll i = 0;i<n;i++){
        ll u, v;
        cin >> u >> v;
        a[i]=u-v;
        if(i) a[i]+=a[i-1];
    }
    priority_queue<ll> pq;
    ll res=0;
    for(ll i = 0;i+1<n;i++){
        if(a[i]<0) res+=-a[i], a[i]=0;
        if(a[i]>a[n-1]) res+=a[i]-a[n-1], a[i]=a[n-1];
        pq.push(a[i]);
        if(pq.top()>a[i]){
            res+=pq.top()-a[i];
            pq.pop();
            pq.push(a[i]);
        }
    }
    cout<<res;
}

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