oj.uz

Submission #940896

# Submission time Handle Problem Language Result Execution time Memory
940896 2024-03-08T01:44:52 Z 12345678 Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 73 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';
        }
        else
        {
            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 if (d[i]<=0) res+=pq.top()-d[i], pq.pop();
            else res+=pq.top()-d[i], pq.push(max(0ll, d[i])), pq.push(max(0ll, d[i])), pq.pop();
        }
        //priority_queue<ll> tmp=pq;
        //cout<<"pq "<<res<<':';
        //while (!tmp.empty()) cout<<tmp.top()<<' ', tmp.pop();
        //cout<<'\n';
        //cout<<i<<' '<<res<<'\n';
    }
    cout<<res;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4600 KB Output is correct
4 Correct 6 ms 9052 KB Output is correct
5 Correct 11 ms 11524 KB Output is correct
6 Correct 34 ms 14200 KB Output is correct
7 Correct 73 ms 18772 KB Output is correct
8 Correct 53 ms 17004 KB Output is correct
9 Correct 53 ms 16376 KB Output is correct
10 Correct 39 ms 13912 KB Output is correct
11 Correct 57 ms 13952 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4600 KB Output is correct
4 Correct 6 ms 9052 KB Output is correct
5 Correct 11 ms 11524 KB Output is correct
6 Correct 34 ms 14200 KB Output is correct
7 Correct 73 ms 18772 KB Output is correct
8 Correct 53 ms 17004 KB Output is correct
9 Correct 53 ms 16376 KB Output is correct
10 Correct 39 ms 13912 KB Output is correct
11 Correct 57 ms 13952 KB Output is correct
12 Incorrect 17 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 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 4444 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4600 KB Output is correct
4 Correct 1 ms 4440 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 4444 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4600 KB Output is correct
4 Correct 1 ms 4440 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 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 6 ms 9052 KB Output is correct
12 Correct 11 ms 11524 KB Output is correct
13 Correct 34 ms 14200 KB Output is correct
14 Correct 73 ms 18772 KB Output is correct
15 Correct 53 ms 17004 KB Output is correct
16 Correct 53 ms 16376 KB Output is correct
17 Correct 39 ms 13912 KB Output is correct
18 Correct 57 ms 13952 KB Output is correct
19 Incorrect 17 ms 12376 KB Output isn't correct
20 Halted 0 ms 0 KB -