Submission #633071

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
633071	2022-08-21T14:23:57 Z	karolb2011	Potatoes and fertilizers (LMIO19_bulves)	Python 3	64 / 100	1000 ms	51632 KB

bulves

import sys
import heapq as hq
input = sys.stdin.readline
n=int(input())
t=0
p=0
s=[]
ww=0
z=[]
for i in range(n):
    pi,bi=list(map(int,input().split()))
    p+=pi-bi
    s.append(p)
if p==0:
    for c in s:
        ww+=abs(c)
elif p==1:
    for c in s:
        if c>=1:
            ww+=c
            t+=c-1
        else:
            ww-=c
            t-=c-1
        z.append(ww-t)
    ww=min(t,min(z)+t)
        
else:
    w=[]
    for c in s:
        if c<0:
            ww-=c
            c=0
        elif c>p:
            ww+=c-p
            c=p
        hq.heappush(w,-c)
        if w[0]<-c:
            hq.heappush(w,-c)
            ww+=abs(-hq.heappop(w)-c)
print(ww)

Subtask #1

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2940 KB	Output is correct
2	Correct	21 ms	2936 KB	Output is correct
3	Correct	18 ms	3100 KB	Output is correct
4	Correct	89 ms	4892 KB	Output is correct
5	Correct	163 ms	6992 KB	Output is correct
6	Correct	369 ms	13024 KB	Output is correct
7	Correct	762 ms	23052 KB	Output is correct
8	Correct	768 ms	26684 KB	Output is correct
9	Correct	763 ms	22908 KB	Output is correct
10	Correct	690 ms	13596 KB	Output is correct
11	Correct	701 ms	16556 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2940 KB	Output is correct
2	Correct	21 ms	2936 KB	Output is correct
3	Correct	18 ms	3100 KB	Output is correct
4	Correct	89 ms	4892 KB	Output is correct
5	Correct	163 ms	6992 KB	Output is correct
6	Correct	369 ms	13024 KB	Output is correct
7	Correct	762 ms	23052 KB	Output is correct
8	Correct	768 ms	26684 KB	Output is correct
9	Correct	763 ms	22908 KB	Output is correct
10	Correct	690 ms	13596 KB	Output is correct
11	Correct	701 ms	16556 KB	Output is correct
12	Correct	237 ms	12904 KB	Output is correct
13	Correct	546 ms	26868 KB	Output is correct
14	Correct	946 ms	42680 KB	Output is correct
15	Correct	927 ms	51632 KB	Output is correct
16	Correct	873 ms	46876 KB	Output is correct
17	Correct	830 ms	28584 KB	Output is correct
18	Correct	18 ms	3028 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2940 KB	Output is correct
2	Correct	21 ms	2936 KB	Output is correct
3	Correct	18 ms	3028 KB	Output is correct
4	Correct	13 ms	2836 KB	Output is correct
5	Correct	15 ms	2984 KB	Output is correct
6	Correct	17 ms	3028 KB	Output is correct
7	Correct	20 ms	3112 KB	Output is correct
8	Correct	20 ms	3036 KB	Output is correct
9	Correct	20 ms	3028 KB	Output is correct
10	Correct	18 ms	3192 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2940 KB	Output is correct
2	Correct	21 ms	2936 KB	Output is correct
3	Correct	18 ms	3100 KB	Output is correct
4	Correct	13 ms	2836 KB	Output is correct
5	Correct	15 ms	2984 KB	Output is correct
6	Correct	17 ms	3028 KB	Output is correct
7	Correct	20 ms	3112 KB	Output is correct
8	Correct	20 ms	3036 KB	Output is correct
9	Correct	20 ms	3028 KB	Output is correct
10	Correct	18 ms	3192 KB	Output is correct
11	Correct	18 ms	3028 KB	Output is correct
12	Correct	20 ms	3052 KB	Output is correct
13	Correct	21 ms	3108 KB	Output is correct
14	Correct	21 ms	3156 KB	Output is correct
15	Correct	22 ms	3100 KB	Output is correct
16	Correct	19 ms	3156 KB	Output is correct
17	Correct	19 ms	3144 KB	Output is correct
18	Correct	20 ms	3096 KB	Output is correct

Subtask #5

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2940 KB	Output is correct
2	Correct	21 ms	2936 KB	Output is correct
3	Correct	18 ms	3100 KB	Output is correct
4	Correct	13 ms	2836 KB	Output is correct
5	Correct	15 ms	2984 KB	Output is correct
6	Correct	17 ms	3028 KB	Output is correct
7	Correct	20 ms	3112 KB	Output is correct
8	Correct	20 ms	3036 KB	Output is correct
9	Correct	20 ms	3028 KB	Output is correct
10	Correct	18 ms	3192 KB	Output is correct
11	Correct	89 ms	4892 KB	Output is correct
12	Correct	163 ms	6992 KB	Output is correct
13	Correct	369 ms	13024 KB	Output is correct
14	Correct	762 ms	23052 KB	Output is correct
15	Correct	768 ms	26684 KB	Output is correct
16	Correct	763 ms	22908 KB	Output is correct
17	Correct	690 ms	13596 KB	Output is correct
18	Correct	701 ms	16556 KB	Output is correct
19	Correct	237 ms	12904 KB	Output is correct
20	Correct	546 ms	26868 KB	Output is correct
21	Correct	946 ms	42680 KB	Output is correct
22	Correct	927 ms	51632 KB	Output is correct
23	Correct	873 ms	46876 KB	Output is correct
24	Correct	830 ms	28584 KB	Output is correct
25	Correct	20 ms	3052 KB	Output is correct
26	Correct	21 ms	3108 KB	Output is correct
27	Correct	21 ms	3156 KB	Output is correct
28	Correct	22 ms	3100 KB	Output is correct
29	Correct	19 ms	3156 KB	Output is correct
30	Correct	19 ms	3144 KB	Output is correct
31	Correct	20 ms	3096 KB	Output is correct
32	Correct	18 ms	3028 KB	Output is correct
33	Correct	345 ms	14516 KB	Output is correct
34	Correct	823 ms	30748 KB	Output is correct
35	Execution timed out	1093 ms	41016 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-