oj.uz

Submission #770857

# Submission time Handle Problem Language Result Execution time Memory
770857 2023-07-02T05:04:52 Z The_Samurai Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 133 ms 22672 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 10 ms 2088 KB Output is correct
5 Correct 20 ms 4052 KB Output is correct
6 Correct 41 ms 7880 KB Output is correct
7 Correct 133 ms 22672 KB Output is correct
8 Correct 97 ms 20820 KB Output is correct
9 Correct 119 ms 20204 KB Output is correct
10 Correct 83 ms 17892 KB Output is correct
11 Correct 83 ms 17872 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 10 ms 2088 KB Output is correct
5 Correct 20 ms 4052 KB Output is correct
6 Correct 41 ms 7880 KB Output is correct
7 Correct 133 ms 22672 KB Output is correct
8 Correct 97 ms 20820 KB Output is correct
9 Correct 119 ms 20204 KB Output is correct
10 Correct 83 ms 17892 KB Output is correct
11 Correct 83 ms 17872 KB Output is correct
12 Incorrect 26 ms 5256 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -