제출 #1265890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265890		Wael	Potatoes and fertilizers (LMIO19_bulves)	C++20	100 / 100	110 ms	12464 KiB

bulves

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr i64 inf = 1E18;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    
    i64 ans = 0;
    i64 k = 0;
    priority_queue<array<i64, 2>, vector<array<i64, 2>>, greater<>> pq;
    pq.push({0, inf});
    for (int i = 0; i < n; ++i) {
        k += b[i] - a[i];
        pq.push({k, 2});
        auto [v, c] = pq.top();
        ans += k - v;
        pq.pop();
        --c;
        if (c > 0) {
            pq.push({v, c});
        }
    }
    while (!pq.empty() && pq.top()[0] < k) {
        ans += pq.top()[1] * (k - pq.top()[0]);
        pq.pop();
    }
    
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    //cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

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