oj.uz

Submission #896535

# Submission time Handle Problem Language Result Execution time Memory
896535 2024-01-01T15:56:55 Z piotrkkskalisz Potatoes and fertilizers (LMIO19_bulves) C++14
0 / 100
 25 ms 2776 KB 
#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()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 11 ms 1504 KB Output is correct
5 Correct 25 ms 2776 KB Output is correct
6 Runtime error 13 ms 2140 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 11 ms 1504 KB Output is correct
5 Correct 25 ms 2776 KB Output is correct
6 Runtime error 13 ms 2140 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 36.0

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