Submission #578551

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

using namespace std;

int n;
int v[200005];

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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 18 ms 5244 KB Output is correct
5 Correct 29 ms 10368 KB Output is correct
6 Runtime error 35 ms 6456 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 18 ms 5244 KB Output is correct
5 Correct 29 ms 10368 KB Output is correct
6 Runtime error 35 ms 6456 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 328 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 328 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 328 KB Output isn't correct
6 Halted 0 ms 0 KB -