oj.uz

Submission #940447

# Submission time Handle Problem Language Result Execution time Memory
940447 2024-03-07T09:25:22 Z 12345678 Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 63 ms 18772 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e5+5;
ll n, a[nx], b[nx], d[nx], res;
priority_queue<ll> pq;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i]>>b[i], d[i]=d[i-1]+a[i]-b[i];
    for (int i=1; i<n; i++)
    {
        //cout<<"val "<<i<<' '<<d[i]<<' '<<d[n]<<'\n';
        if (pq.empty())
        {
            if (d[i]<=0) res-=d[i];
            else if (d[i]>=d[n]) res+=d[i]-d[n];
            else pq.push(d[i]);
            //cout<<i<<' '<<res<<'\n';
            continue;
        }
        if (d[i]>=d[n]) res+=(d[i]-d[n]), pq.push(min(d[n], d[i]));
        else if (d[i]>=pq.top()) pq.push(d[i]);
        else res+=pq.top()-d[i], pq.push(max(0ll, d[i])), pq.push(max(0ll, d[i])), pq.pop();
        //cout<<i<<' '<<res<<'\n';
    }
    cout<<res;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 6 ms 9048 KB Output is correct
5 Correct 12 ms 11524 KB Output is correct
6 Correct 36 ms 14160 KB Output is correct
7 Correct 63 ms 18772 KB Output is correct
8 Correct 52 ms 16980 KB Output is correct
9 Correct 54 ms 16212 KB Output is correct
10 Correct 37 ms 13904 KB Output is correct
11 Correct 37 ms 13916 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 6 ms 9048 KB Output is correct
5 Correct 12 ms 11524 KB Output is correct
6 Correct 36 ms 14160 KB Output is correct
7 Correct 63 ms 18772 KB Output is correct
8 Correct 52 ms 16980 KB Output is correct
9 Correct 54 ms 16212 KB Output is correct
10 Correct 37 ms 13904 KB Output is correct
11 Correct 37 ms 13916 KB Output is correct
12 Incorrect 19 ms 12376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4572 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Incorrect 1 ms 4444 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4572 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Incorrect 1 ms 4444 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4572 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 6 ms 9048 KB Output is correct
12 Correct 12 ms 11524 KB Output is correct
13 Correct 36 ms 14160 KB Output is correct
14 Correct 63 ms 18772 KB Output is correct
15 Correct 52 ms 16980 KB Output is correct
16 Correct 54 ms 16212 KB Output is correct
17 Correct 37 ms 13904 KB Output is correct
18 Correct 37 ms 13916 KB Output is correct
19 Incorrect 19 ms 12376 KB Output isn't correct
20 Halted 0 ms 0 KB -