oj.uz

Submission #422157

# Submission time Handle Problem Language Result Execution time Memory
422157 2021-06-09T19:16:44 Z JerryLiu06 Potatoes and fertilizers (LMIO19_bulves) C++17
100 / 100
 172 ms 15244 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
const int MOD = 1e9 + 7;
const int MX = 5e5 + 10;
const ll INF = 1e18;

int N; ll D[MX]; priority_queue<ll> Q; ll ans;

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

    cin >> N; FOR(i, 1, N + 1) {
        int A, B; cin >> A >> B; D[i] = A - B + D[i - 1];
    }
   // FOR(i, 1, N + 1) cout << D[i] << "\n";
  
    FOR(i, 1, N + 1) {
        if (D[i] < 0) { ans -= D[i]; D[i] = 0; }
        
        if (D[i] > D[N]) { ans += D[i] - D[N]; D[i] = D[N]; }
        
        Q.push(D[i]); if (Q.top() > D[i]) {
            ans += Q.top() - D[i]; Q.pop(); Q.push(D[i]);
        }
    }
    cout << ans;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 11 ms 1360 KB Output is correct
5 Correct 18 ms 2276 KB Output is correct
6 Correct 56 ms 4340 KB Output is correct
7 Correct 107 ms 8352 KB Output is correct
8 Correct 96 ms 8380 KB Output is correct
9 Correct 101 ms 12608 KB Output is correct
10 Correct 76 ms 10300 KB Output is correct
11 Correct 83 ms 10376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 11 ms 1360 KB Output is correct
5 Correct 18 ms 2276 KB Output is correct
6 Correct 56 ms 4340 KB Output is correct
7 Correct 107 ms 8352 KB Output is correct
8 Correct 96 ms 8380 KB Output is correct
9 Correct 101 ms 12608 KB Output is correct
10 Correct 76 ms 10300 KB Output is correct
11 Correct 83 ms 10376 KB Output is correct
12 Correct 29 ms 4040 KB Output is correct
13 Correct 69 ms 10940 KB Output is correct
14 Correct 115 ms 15232 KB Output is correct
15 Correct 99 ms 13352 KB Output is correct
16 Correct 101 ms 12600 KB Output is correct
17 Correct 91 ms 10400 KB Output is correct
18 Correct 1 ms 332 KB Output is correct

Subtask #3
20.0 / 20.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 11 ms 1360 KB Output is correct
12 Correct 18 ms 2276 KB Output is correct
13 Correct 56 ms 4340 KB Output is correct
14 Correct 107 ms 8352 KB Output is correct
15 Correct 96 ms 8380 KB Output is correct
16 Correct 101 ms 12608 KB Output is correct
17 Correct 76 ms 10300 KB Output is correct
18 Correct 83 ms 10376 KB Output is correct
19 Correct 29 ms 4040 KB Output is correct
20 Correct 69 ms 10940 KB Output is correct
21 Correct 115 ms 15232 KB Output is correct
22 Correct 99 ms 13352 KB Output is correct
23 Correct 101 ms 12600 KB Output is correct
24 Correct 91 ms 10400 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 41 ms 4152 KB Output is correct
34 Correct 101 ms 10928 KB Output is correct
35 Correct 172 ms 15164 KB Output is correct
36 Correct 157 ms 12804 KB Output is correct
37 Correct 101 ms 13276 KB Output is correct
38 Correct 156 ms 15244 KB Output is correct
39 Correct 103 ms 11288 KB Output is correct
40 Correct 105 ms 10944 KB Output is correct
41 Correct 98 ms 10336 KB Output is correct
42 Correct 99 ms 10384 KB Output is correct
43 Correct 100 ms 10416 KB Output is correct
44 Correct 102 ms 10388 KB Output is correct
45 Correct 126 ms 15152 KB Output is correct
46 Correct 93 ms 10688 KB Output is correct
47 Correct 124 ms 10188 KB Output is correct