oj.uz

Submission #591726

# Submission time Handle Problem Language Result Execution time Memory
591726 2022-07-07T19:29:41 Z piOOE Potatoes and fertilizers (LMIO19_bulves) C++17
100 / 100
 138 ms 15232 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
 
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;
 
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
 
#define ll long long
#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) -  begin(x))
#define ld long double
#define sz(s) (int) size(s)
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define mt make_tuple
#define int128 __int128
 
 
template<typename T>
bool ckmin(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
 
template<typename T>
bool ckmax(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
 
int bit(int x, int b) {
    return (x >> b) & 1;
}
 
 
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
 
const ll infL = 3e18;
const int infI = 1e9 + 7;
const int N = 500001;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
 
ll A[N];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        A[i] = (i ? A[i - 1] : 0) + a - b;
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if (A[i] < 0) {
            //it means that on our prefix sum(b) > sum(a) so we have to take some a's from right and put them here
            ans += -A[i];
            A[i] = 0;
        }
        if (A[i] > A[n - 1]) {
            //it means that now we have to take some from here and put them righter
            ans += A[i] - A[n - 1];
            A[i] = A[n - 1];
        }
    }
    //now everything on every prefix is alright so let's go to solve classic problem about making this array non-decreasing
    priority_queue<ll> pq;
    for (int i = 0; i < n; ++i) {
        pq.push(A[i]);
        pq.push(A[i]);
        ans += pq.top() - A[i];
        pq.pop();
    }
    cout << ans;
    return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 1624 KB Output is correct
5 Correct 15 ms 2896 KB Output is correct
6 Correct 48 ms 7836 KB Output is correct
7 Correct 97 ms 15096 KB Output is correct
8 Correct 88 ms 13280 KB Output is correct
9 Correct 90 ms 12640 KB Output is correct
10 Correct 75 ms 10396 KB Output is correct
11 Correct 71 ms 10412 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 1624 KB Output is correct
5 Correct 15 ms 2896 KB Output is correct
6 Correct 48 ms 7836 KB Output is correct
7 Correct 97 ms 15096 KB Output is correct
8 Correct 88 ms 13280 KB Output is correct
9 Correct 90 ms 12640 KB Output is correct
10 Correct 75 ms 10396 KB Output is correct
11 Correct 71 ms 10412 KB Output is correct
12 Correct 26 ms 4060 KB Output is correct
13 Correct 63 ms 10880 KB Output is correct
14 Correct 103 ms 15232 KB Output is correct
15 Correct 113 ms 13376 KB Output is correct
16 Correct 87 ms 12728 KB Output is correct
17 Correct 76 ms 10432 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 360 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 360 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 388 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 360 KB Output is correct
11 Correct 9 ms 1624 KB Output is correct
12 Correct 15 ms 2896 KB Output is correct
13 Correct 48 ms 7836 KB Output is correct
14 Correct 97 ms 15096 KB Output is correct
15 Correct 88 ms 13280 KB Output is correct
16 Correct 90 ms 12640 KB Output is correct
17 Correct 75 ms 10396 KB Output is correct
18 Correct 71 ms 10412 KB Output is correct
19 Correct 26 ms 4060 KB Output is correct
20 Correct 63 ms 10880 KB Output is correct
21 Correct 103 ms 15232 KB Output is correct
22 Correct 113 ms 13376 KB Output is correct
23 Correct 87 ms 12728 KB Output is correct
24 Correct 76 ms 10432 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 388 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 36 ms 4148 KB Output is correct
34 Correct 101 ms 10884 KB Output is correct
35 Correct 136 ms 15172 KB Output is correct
36 Correct 126 ms 12732 KB Output is correct
37 Correct 108 ms 13260 KB Output is correct
38 Correct 138 ms 15140 KB Output is correct
39 Correct 84 ms 11352 KB Output is correct
40 Correct 93 ms 10948 KB Output is correct
41 Correct 80 ms 10500 KB Output is correct
42 Correct 79 ms 10348 KB Output is correct
43 Correct 83 ms 10364 KB Output is correct
44 Correct 81 ms 10436 KB Output is correct
45 Correct 113 ms 15212 KB Output is correct
46 Correct 107 ms 10816 KB Output is correct
47 Correct 86 ms 10276 KB Output is correct