oj.uz

Submission #578552

# Submission time Handle Problem Language Result Execution time Memory
578552 2022-06-17T08:55:54 Z Tenis0206 Potatoes and fertilizers (LMIO19_bulves) C++11
24 / 100
 175 ms 54108 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;
int v[500005];

struct slopetrick
{
    int a,b;
    priority_queue<int> *s;
    slopetrick()
    {
        a = b = 0;
        s = new priority_queue<int>;
    }
    void operator += (slopetrick other)
    {
        a += other.a;
        b += other.b;
        if(s->size()<other.s->size())
        {
            swap(s,other.s);
        }
        while(other.s->size())
        {
            s->push(other.s->top());
            other.s->pop();
        }
    }
    void elim()
    {
        while(a>0)
        {
            b += s->top();
            s->pop();
            --a;
        }
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        v[i] = v[i-1] + a - b;
    }
    slopetrick rez;
    int val = 0;
    for(int i=1; i<n; i++)
    {
        slopetrick aux;
        if(v[i]<0)
        {
            val += abs(v[i]);
            aux.a = 1, aux.b = 0;
            aux.s->push(0);
            aux.s->push(0);
        }
        else if(v[i]>v[n])
        {
            val += v[i] - v[n];
            aux.a = 1, aux.b = v[n];
            aux.s->push(v[n]);
            aux.s->push(v[n]);
        }
        else
        {
            aux.a = 1, aux.b = -v[i];
            aux.s->push(v[i]);
            aux.s->push(v[i]);
        }
        rez += aux;
        rez.elim();
    }
    val += rez.b;
    cout<<val<<'\n';
    return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 19 ms 4976 KB Output is correct
5 Correct 32 ms 9672 KB Output is correct
6 Correct 92 ms 24196 KB Output is correct
7 Correct 175 ms 54108 KB Output is correct
8 Correct 165 ms 52064 KB Output is correct
9 Correct 169 ms 51452 KB Output is correct
10 Correct 135 ms 49192 KB Output is correct
11 Correct 131 ms 49136 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 19 ms 4976 KB Output is correct
5 Correct 32 ms 9672 KB Output is correct
6 Correct 92 ms 24196 KB Output is correct
7 Correct 175 ms 54108 KB Output is correct
8 Correct 165 ms 52064 KB Output is correct
9 Correct 169 ms 51452 KB Output is correct
10 Correct 135 ms 49192 KB Output is correct
11 Correct 131 ms 49136 KB Output is correct
12 Incorrect 44 ms 13764 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -