Submission #770857

#	Time	Username	Problem	Language	Result	Execution time	Memory
770857		The_Samurai	Potatoes and fertilizers (LMIO19_bulves)	C++17	24 / 100	133 ms	22672 KiB

bulves

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    set<int> pos;
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
        if (a[i].first > a[i].second) {
            pos.insert(i);
        }
    }
    int j = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i].first >= a[i].second) {
            continue;
        }
        while (a[i].first < a[i].second) {
            while (j < i and a[j].first <= a[j].second) {
                j++;
            }
            if (j != i) {
                int x = min(a[i].second - a[i].first, a[j].first - a[j].second);
                a[i].first += x;
                a[j].first -= x;
                ans += 1ll * x * abs(j - i);
            } else {
                break;
            }
        }
        while (a[i].first < a[i].second) {
            int k = *pos.lower_bound(i);
            int x = min(a[i].second - a[i].first, a[k].first - a[k].second);
            a[i].first += x;
            a[k].first -= x;
            ans += 1ll * x * abs(k - i);
            if (a[k].first == a[k].second) {
                pos.erase(k);
            }
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    int queries = 1;
#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> queries;
#else
    //    cin >> queries;
#endif

    for (int test_case = 1; test_case <= queries; test_case++) {
        solve();
        cout << '\n';
    }
}

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