답안 #144666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144666	2019-08-17T10:51:18 Z	brcode	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	727 ms	19400 KB

bulves

#include <iostream>
#include <queue>
using namespace std;
const long long MAXN = 5e5+5;
long long ans;
long long pref[MAXN];
long long c[MAXN];
long long n;
priority_queue<long long> pq;

int main(){

    cin>>n;
    for(long long i=1;i<=n;i++){
        long long a,b;
        cin>>a>>b;
        c[i] = a-b;
        pref[i] = pref[i-1]+c[i];
    }
    for(long long i=1;i<=n;i++){
        if(pref[i]<0){
            ans+=abs(pref[i]);
            pref[i] = 0;
        }
        if(pref[i]>pref[n]){
            ans+=pref[i]-pref[n];
            pref[i]=pref[n];
        }
    }

   
    for(long long i=1;i<=n;i++){
        if(!pq.empty() && pq.top()>pref[i]){
            ans+=pq.top()-pref[i];
            pq.pop();
            pq.push(pref[i]);
        }
        pq.push(pref[i]);
    }
    cout<<ans<<endl;
}

Subtask #1

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	380 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	40 ms	2136 KB	Output is correct
5	Correct	72 ms	3664 KB	Output is correct
6	Correct	292 ms	9832 KB	Output is correct
7	Correct	567 ms	19256 KB	Output is correct
8	Correct	455 ms	17256 KB	Output is correct
9	Correct	415 ms	16764 KB	Output is correct
10	Correct	274 ms	14404 KB	Output is correct
11	Correct	276 ms	14312 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	380 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	40 ms	2136 KB	Output is correct
5	Correct	72 ms	3664 KB	Output is correct
6	Correct	292 ms	9832 KB	Output is correct
7	Correct	567 ms	19256 KB	Output is correct
8	Correct	455 ms	17256 KB	Output is correct
9	Correct	415 ms	16764 KB	Output is correct
10	Correct	274 ms	14404 KB	Output is correct
11	Correct	276 ms	14312 KB	Output is correct
12	Correct	145 ms	5228 KB	Output is correct
13	Correct	362 ms	13376 KB	Output is correct
14	Correct	573 ms	19172 KB	Output is correct
15	Correct	472 ms	17240 KB	Output is correct
16	Correct	424 ms	16848 KB	Output is correct
17	Correct	282 ms	14308 KB	Output is correct
18	Correct	4 ms	376 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	4 ms	504 KB	Output is correct
7	Correct	4 ms	504 KB	Output is correct
8	Correct	4 ms	504 KB	Output is correct
9	Correct	4 ms	504 KB	Output is correct
10	Correct	4 ms	376 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	380 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	4 ms	504 KB	Output is correct
8	Correct	4 ms	504 KB	Output is correct
9	Correct	4 ms	504 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	4 ms	376 KB	Output is correct
12	Correct	6 ms	504 KB	Output is correct
13	Correct	6 ms	504 KB	Output is correct
14	Correct	5 ms	504 KB	Output is correct
15	Correct	5 ms	504 KB	Output is correct
16	Correct	4 ms	504 KB	Output is correct
17	Correct	6 ms	504 KB	Output is correct
18	Correct	4 ms	376 KB	Output is correct

Subtask #5

36.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	380 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	4 ms	504 KB	Output is correct
8	Correct	4 ms	504 KB	Output is correct
9	Correct	4 ms	504 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	40 ms	2136 KB	Output is correct
12	Correct	72 ms	3664 KB	Output is correct
13	Correct	292 ms	9832 KB	Output is correct
14	Correct	567 ms	19256 KB	Output is correct
15	Correct	455 ms	17256 KB	Output is correct
16	Correct	415 ms	16764 KB	Output is correct
17	Correct	274 ms	14404 KB	Output is correct
18	Correct	276 ms	14312 KB	Output is correct
19	Correct	145 ms	5228 KB	Output is correct
20	Correct	362 ms	13376 KB	Output is correct
21	Correct	573 ms	19172 KB	Output is correct
22	Correct	472 ms	17240 KB	Output is correct
23	Correct	424 ms	16848 KB	Output is correct
24	Correct	282 ms	14308 KB	Output is correct
25	Correct	4 ms	376 KB	Output is correct
26	Correct	6 ms	504 KB	Output is correct
27	Correct	6 ms	504 KB	Output is correct
28	Correct	5 ms	504 KB	Output is correct
29	Correct	5 ms	504 KB	Output is correct
30	Correct	4 ms	504 KB	Output is correct
31	Correct	6 ms	504 KB	Output is correct
32	Correct	157 ms	5176 KB	Output is correct
33	Correct	381 ms	13356 KB	Output is correct
34	Correct	643 ms	19244 KB	Output is correct
35	Correct	495 ms	16748 KB	Output is correct
36	Correct	476 ms	17296 KB	Output is correct
37	Correct	727 ms	19304 KB	Output is correct
38	Correct	354 ms	15332 KB	Output is correct
39	Correct	368 ms	14536 KB	Output is correct
40	Correct	301 ms	14388 KB	Output is correct
41	Correct	303 ms	14308 KB	Output is correct
42	Correct	309 ms	14440 KB	Output is correct
43	Correct	308 ms	14324 KB	Output is correct
44	Correct	586 ms	19400 KB	Output is correct
45	Correct	301 ms	14820 KB	Output is correct
46	Correct	340 ms	13404 KB	Output is correct
47	Correct	4 ms	376 KB	Output is correct