Submission #633067

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
633067	2022-08-21T14:18:18 Z	karolb2011	Potatoes and fertilizers (LMIO19_bulves)	Python 3	24 / 100	773 ms	26792 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)
    print(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	13 ms	2924 KB	Output is correct
2	Correct	21 ms	2972 KB	Output is correct
3	Correct	19 ms	3064 KB	Output is correct
4	Correct	89 ms	4884 KB	Output is correct
5	Correct	186 ms	6900 KB	Output is correct
6	Correct	426 ms	12988 KB	Output is correct
7	Correct	773 ms	22892 KB	Output is correct
8	Correct	731 ms	26792 KB	Output is correct
9	Correct	767 ms	22764 KB	Output is correct
10	Correct	743 ms	13632 KB	Output is correct
11	Correct	726 ms	16472 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2924 KB	Output is correct
2	Correct	21 ms	2972 KB	Output is correct
3	Correct	19 ms	3064 KB	Output is correct
4	Correct	89 ms	4884 KB	Output is correct
5	Correct	186 ms	6900 KB	Output is correct
6	Correct	426 ms	12988 KB	Output is correct
7	Correct	773 ms	22892 KB	Output is correct
8	Correct	731 ms	26792 KB	Output is correct
9	Correct	767 ms	22764 KB	Output is correct
10	Correct	743 ms	13632 KB	Output is correct
11	Correct	726 ms	16472 KB	Output is correct
12	Incorrect	255 ms	12900 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2924 KB	Output is correct
2	Correct	21 ms	2972 KB	Output is correct
3	Correct	13 ms	2900 KB	Output is correct
4	Correct	16 ms	2992 KB	Output is correct
5	Correct	16 ms	2976 KB	Output is correct
6	Correct	19 ms	3112 KB	Output is correct
7	Correct	19 ms	3036 KB	Output is correct
8	Correct	21 ms	3096 KB	Output is correct
9	Correct	22 ms	3116 KB	Output is correct
10	Incorrect	18 ms	3060 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2924 KB	Output is correct
2	Correct	21 ms	2972 KB	Output is correct
3	Correct	19 ms	3064 KB	Output is correct
4	Correct	13 ms	2900 KB	Output is correct
5	Correct	16 ms	2992 KB	Output is correct
6	Correct	16 ms	2976 KB	Output is correct
7	Correct	19 ms	3112 KB	Output is correct
8	Correct	19 ms	3036 KB	Output is correct
9	Correct	21 ms	3096 KB	Output is correct
10	Correct	22 ms	3116 KB	Output is correct
11	Incorrect	18 ms	3060 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2924 KB	Output is correct
2	Correct	21 ms	2972 KB	Output is correct
3	Correct	19 ms	3064 KB	Output is correct
4	Correct	13 ms	2900 KB	Output is correct
5	Correct	16 ms	2992 KB	Output is correct
6	Correct	16 ms	2976 KB	Output is correct
7	Correct	19 ms	3112 KB	Output is correct
8	Correct	19 ms	3036 KB	Output is correct
9	Correct	21 ms	3096 KB	Output is correct
10	Correct	22 ms	3116 KB	Output is correct
11	Correct	89 ms	4884 KB	Output is correct
12	Correct	186 ms	6900 KB	Output is correct
13	Correct	426 ms	12988 KB	Output is correct
14	Correct	773 ms	22892 KB	Output is correct
15	Correct	731 ms	26792 KB	Output is correct
16	Correct	767 ms	22764 KB	Output is correct
17	Correct	743 ms	13632 KB	Output is correct
18	Correct	726 ms	16472 KB	Output is correct
19	Incorrect	255 ms	12900 KB	Output isn't correct
20	Halted	0 ms	0 KB	-