oj.uz

Submission #450312

# Submission time Handle Problem Language Result Execution time Memory
450312 2021-08-02T13:41:23 Z cmorax Potatoes and fertilizers (LMIO19_bulves) C++17
0 / 100
 395 ms 15208 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int N;
ll fst = 0; // value of DP function at 0
priority_queue<ll> points; // points where DP function changes slope

int main() {
    cin >> N;
    vector<ll> dif(N+1);
    for (int i = 1; i <= N; ++i) {
        int a,b; cin >> a >> b;
        dif[i] = a-b+dif[i-1];
    }
    assert(dif[N] >= 0); // assume solution exists
    for (int i = 1; i < N; ++i) {
        if (dif[i] < 0) fst -= dif[i], dif[i] = 0;
        points.push(dif[i]); points.push(dif[i]);

        fst += points.top() - dif[i];

        points.pop();
    }

    if(N == 1){
        cout << 0 << endl;
        return 0;
    }

    int mult = 0;
    int last = points.top();
    while(!points.empty()){
        int at = points.top();
        
        //cout << "/ " << at << " " << last << " " << mult << endl;

        if(at <= dif[N]){
            fst += (last - dif[N]) * mult;
            break;
        }

        fst += (last - at) * mult;

        last = at;
        mult ++;
        points.pop();
    }

    cout << fst << endl;
}

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 30 ms 1656 KB Output is correct
5 Correct 62 ms 2852 KB Output is correct
6 Correct 231 ms 7736 KB Output is correct
7 Correct 395 ms 15208 KB Output is correct
8 Incorrect 336 ms 13252 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 30 ms 1656 KB Output is correct
5 Correct 62 ms 2852 KB Output is correct
6 Correct 231 ms 7736 KB Output is correct
7 Correct 395 ms 15208 KB Output is correct
8 Incorrect 336 ms 13252 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 36.0

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