Submission #601842

#	Time	Username	Problem	Language	Result	Execution time	Memory
601842		keta_tsimakuridze	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	172 ms	15048 KiB

bulves

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 5e5 + 5, mod = 1e9 + 7; // !
int t, d[N];
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    // ans = jami(ai[i] - a[i]) = jami (d'[i] - d[i]);
    priority_queue<int, vector<int>, less<int> > q;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        // a' - b >= 0 yvelastvis => d'[i + 1] >= d'[i]
        d[i] = d[i - 1] + a - b;
        if(d[i] < 0) ans += -d[i];
        q.push(max(0ll, d[i]));
        q.push(max(0ll, d[i]));
        ans += q.top() - (max(0ll, d[i]));
        q.pop();
    }
    q.push(d[n]);
    int k = 1;
    while(q.top() != d[n]) {
        int x = q.top();
        q.pop();
        ans += k * (x - q.top());
        ++k;
    }
    cout << ans;
 }

Compilation message (stderr)

bulves.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){
      | ^~~~

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