Submission #896532

#	Time	Username	Problem	Language	Result	Execution time	Memory
896532		piotrkkskalisz	Potatoes and fertilizers (LMIO19_bulves)	C++14	0 / 100	49 ms	3532 KiB

bulves

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

const int M = 1e5 + 10;
long long pref[M];
long long f0;

priority_queue <long long> P;
stack <long long> stos;

int main()
{
    int n, nawoz, ziemniak;
    cin >> n;

    pref[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        cin >> nawoz >> ziemniak;
        pref[i] = pref[i - 1] + nawoz - ziemniak;
    }

    f0 = abs(pref[1]);
    if (pref[1] < 0)    P.push(0);
    else P.push(pref[1]);

    long long p;

    //cout << "sumy prefixowe \n" << pref[1] << ' ';
    for (int i = 2; i < n; i++)
    {
        //cout << pref[i] << ' ';
        f0 += abs(pref[i]);
        p = P.top();
        if (pref[i] < 0)// pref[i] = 0;
        {
            P.push(0);
            continue;
        }
        if (p <= pref[i])
        {
            P.push(pref[i]);
            continue;
        }
        P.pop();

        P.push(pref[i]);
        P.push(pref[i]);

    }
    //cout << '\n';
    //cout << "rozmiar: " << P.size() << '\n';
    while (!P.empty())
    {
        p = P.top();
        P.pop();
        stos.push(p);
    }

    long long p1 = 0;
    long long p2;
    long long wynik = f0;

    //cout << "start " << f0 << '\n';
    //cout << "punkty: ";
    for (int i = n - 1; i > 0; i--)
    {
        p2 = p1;
        p1 = stos.top();
        //cout <<  p1 << ' ';
        if (p1 > pref[n])
        {
            wynik -= i * (pref[n] - p2);
            break;
        }
        stos.pop();
        wynik -= i * (p1 - p2);

    }
    //cout << "\nwynik: ";
    cout << wynik;
    return 0;


}

/*
7
2 0
2 0
2 0
0 5
2 0
2 0
7 0

6
6 0
1 0
0 3
1 0
0 3
1 0

5
0 5
1 0
1 0
0 5
10 0

4
0 5
7 0
0 5
3 0
1+1+4 + 4*4=24
*/

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36