Submission #578553

#	Time	Username	Problem	Language	Result	Execution time	Memory
578553		Tenis0206	Potatoes and fertilizers (LMIO19_bulves)	C++11	100 / 100	247 ms	54008 KiB

bulves

#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 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36