oj.uz

Submission #578408

# Submission time Handle Problem Language Result Execution time Memory
578408 2022-06-16T16:58:34 Z Alexandruabcde Potatoes and fertilizers (LMIO19_bulves) C++14
30 / 100
 626 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 5e5 + 5;
typedef long long LL;

struct SlopeTrick {
    LL a, b;

    priority_queue <LL> *H;

    SlopeTrick () {
        a = b = 0;

        H = new priority_queue<LL>;
    }

    SlopeTrick operator += (SlopeTrick other) {
        a += other.a;
        b += other.b;

        if (H->size() > other.H->size())
            swap(H, other.H);

        while (!other.H->empty()) {
            H->push(other.H->top());
            other.H->pop();
        }

        while (a > 0) {
            -- a;
            b += H->top();
            H->pop();
        }

        return *this;
    }

    SlopeTrick Evaluate () {
        while (a > 0) {
            -- a;
            b += H->top();
            H->pop();
        }

        return *this;
    }
};

int N;
LL D[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i <= N; ++ i ) {
        LL A, B;
        cin >> A >> B;

        D[i] = D[i-1] + A - B;
    }
}

void Solve () {
    SlopeTrick ans;
    for (int i = 1; i < N; ++ i ) {
        SlopeTrick aux;
        aux.a = 1;

        if (D[i] > D[N]) {
            ans.b += (D[i] - D[N]);
            D[i] = D[N];
        }
        aux.b = -D[i];
        if (D[i] < 0) D[i] = 0;

        aux.H->push(D[i]);
        aux.H->push(D[i]);

        ans += aux;
    }

    ans.Evaluate();

    cout << ans.b << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 91 ms 44072 KB Output is correct
3 Correct 91 ms 44036 KB Output is correct
4 Runtime error 626 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 91 ms 44072 KB Output is correct
3 Correct 91 ms 44036 KB Output is correct
4 Runtime error 626 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 91 ms 44072 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 29 ms 5608 KB Output is correct
5 Correct 65 ms 12468 KB Output is correct
6 Correct 292 ms 43908 KB Output is correct
7 Correct 173 ms 44080 KB Output is correct
8 Correct 274 ms 44016 KB Output is correct
9 Correct 97 ms 43980 KB Output is correct
10 Correct 92 ms 44028 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 91 ms 44072 KB Output is correct
3 Correct 91 ms 44036 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 29 ms 5608 KB Output is correct
6 Correct 65 ms 12468 KB Output is correct
7 Correct 292 ms 43908 KB Output is correct
8 Correct 173 ms 44080 KB Output is correct
9 Correct 274 ms 44016 KB Output is correct
10 Correct 97 ms 43980 KB Output is correct
11 Correct 92 ms 44028 KB Output is correct
12 Correct 117 ms 20496 KB Output is correct
13 Correct 278 ms 44076 KB Output is correct
14 Correct 269 ms 44112 KB Output is correct
15 Correct 265 ms 43980 KB Output is correct
16 Correct 224 ms 44140 KB Output is correct
17 Correct 210 ms 44056 KB Output is correct
18 Correct 104 ms 44012 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 91 ms 44072 KB Output is correct
3 Correct 91 ms 44036 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 29 ms 5608 KB Output is correct
6 Correct 65 ms 12468 KB Output is correct
7 Correct 292 ms 43908 KB Output is correct
8 Correct 173 ms 44080 KB Output is correct
9 Correct 274 ms 44016 KB Output is correct
10 Correct 97 ms 43980 KB Output is correct
11 Runtime error 626 ms 262144 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -