Submission #1356987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356987		Irate	Potatoes and fertilizers (LMIO19_bulves)	C++20	100 / 100	127 ms	12488 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int>a(n + 1), b(n + 1);
    vector<long long>p(n + 1);
    for(int i = 1;i <= n;++i){
        cin >> a[i] >> b[i];
        p[i] = p[i - 1] + (a[i] - b[i]);
    }
    priority_queue<long long>pq;
    long long dp0 = 0;
    for(int i = 1;i < n;++i){
        pq.push(p[i]);
        pq.push(p[i]);
        pq.pop();

        dp0 += abs(p[i]);
    }

    while(!pq.empty() && pq.top() >= 0){
        long long point = pq.top();
        dp0 -= min(p[n], point);
        pq.pop();
    }
    cout << dp0 << '\n';

}

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