Submission #415339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
415339	2021-05-31T22:29:41 Z	gmyu	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	249 ms	22924 KB

bulves

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/LMIO19_bulves
*/
#include <iostream>  //cin , couta
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 500007
#define MAXE 100007


bool debug;

int N;
ll a[MAXV], b[MAXV], ps[MAXV];

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    ll ans = 0LL;
    priority_queue<ll> pq;

    cin >> N;
    for(int i=1;i<N;i++) {
        cin >> a[i] >> b[i];
        ps[i] = (a[i]-b[i]) + ps[i-1];
        if(ps[i] >= 0) {
            ans += ps[i];   /// move downstream
            pq.push(ps[i]); /// option of not moving to next node; move it back from upstream
            pq.push(ps[i]); /// option of not even move anything from 1 .. i
            pq.pop();
        } else {    // do not have extra to move downstream
            ans += -ps[i]; /// borrow those from downstream
            pq.push(0); /// nothing to move to next node
            pq.push(0); /// nothing to cancel
            pq.pop();
        }
    }

    cin >> a[N] >> b[N];
    ps[N] = a[N] - b[N] + ps[N-1];
    for(int i=1; i<=N && !pq.empty(); i++) {
        ans -= min(pq.top(), ps[N]);    /// max you can move from upstream
        pq.pop();
    }

    cout << ans << endl;

    if(debug) cout << endl << "EOL" << endl;

}
/**
6
1 2
0 0
2 0
0 0
0 0
0 1

7
2 0
2 0
2 0
0 5
2 0
2 0
2 0

*/

Subtask #1
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	18 ms	2388 KB	Output is correct
5	Correct	37 ms	4160 KB	Output is correct
6	Correct	126 ms	11576 KB	Output is correct
7	Correct	183 ms	22776 KB	Output is correct
8	Correct	210 ms	20936 KB	Output is correct
9	Correct	185 ms	20280 KB	Output is correct
10	Correct	148 ms	17968 KB	Output is correct
11	Correct	150 ms	17948 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	18 ms	2388 KB	Output is correct
5	Correct	37 ms	4160 KB	Output is correct
6	Correct	126 ms	11576 KB	Output is correct
7	Correct	183 ms	22776 KB	Output is correct
8	Correct	210 ms	20936 KB	Output is correct
9	Correct	185 ms	20280 KB	Output is correct
10	Correct	148 ms	17968 KB	Output is correct
11	Correct	150 ms	17948 KB	Output is correct
12	Correct	56 ms	6048 KB	Output is correct
13	Correct	142 ms	14392 KB	Output is correct
14	Correct	179 ms	22760 KB	Output is correct
15	Correct	212 ms	20936 KB	Output is correct
16	Correct	222 ms	20396 KB	Output is correct
17	Correct	145 ms	18104 KB	Output is correct
18	Correct	2 ms	460 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	1 ms	328 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	1 ms	328 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	3 ms	460 KB	Output is correct
14	Correct	2 ms	460 KB	Output is correct
15	Correct	2 ms	460 KB	Output is correct
16	Correct	2 ms	460 KB	Output is correct
17	Correct	3 ms	460 KB	Output is correct
18	Correct	2 ms	496 KB	Output is correct

Subtask #5
36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	1 ms	328 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	18 ms	2388 KB	Output is correct
12	Correct	37 ms	4160 KB	Output is correct
13	Correct	126 ms	11576 KB	Output is correct
14	Correct	183 ms	22776 KB	Output is correct
15	Correct	210 ms	20936 KB	Output is correct
16	Correct	185 ms	20280 KB	Output is correct
17	Correct	148 ms	17968 KB	Output is correct
18	Correct	150 ms	17948 KB	Output is correct
19	Correct	56 ms	6048 KB	Output is correct
20	Correct	142 ms	14392 KB	Output is correct
21	Correct	179 ms	22760 KB	Output is correct
22	Correct	212 ms	20936 KB	Output is correct
23	Correct	222 ms	20396 KB	Output is correct
24	Correct	145 ms	18104 KB	Output is correct
25	Correct	2 ms	348 KB	Output is correct
26	Correct	3 ms	460 KB	Output is correct
27	Correct	2 ms	460 KB	Output is correct
28	Correct	2 ms	460 KB	Output is correct
29	Correct	2 ms	460 KB	Output is correct
30	Correct	3 ms	460 KB	Output is correct
31	Correct	2 ms	496 KB	Output is correct
32	Correct	2 ms	460 KB	Output is correct
33	Correct	59 ms	6076 KB	Output is correct
34	Correct	144 ms	14344 KB	Output is correct
35	Correct	249 ms	22728 KB	Output is correct
36	Correct	240 ms	20420 KB	Output is correct
37	Correct	207 ms	20876 KB	Output is correct
38	Correct	237 ms	22924 KB	Output is correct
39	Correct	167 ms	18924 KB	Output is correct
40	Correct	178 ms	17456 KB	Output is correct
41	Correct	152 ms	18072 KB	Output is correct
42	Correct	149 ms	17944 KB	Output is correct
43	Correct	146 ms	18148 KB	Output is correct
44	Correct	145 ms	17964 KB	Output is correct
45	Correct	231 ms	22816 KB	Output is correct
46	Correct	174 ms	18416 KB	Output is correct
47	Correct	164 ms	15340 KB	Output is correct

Submission #415339

Compilation message

Subtask #1 24.0 / 24.0

Subtask #2 10.0 / 10.0

Subtask #3 20.0 / 20.0

Subtask #4 10.0 / 10.0

Subtask #5 36.0 / 36.0

Subtask #1
24.0 / 24.0

Subtask #2
10.0 / 10.0

Subtask #3
20.0 / 20.0

Subtask #4
10.0 / 10.0

Subtask #5
36.0 / 36.0