This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import sys
input = sys.stdin.readline
n=int(input())
t=0
p=0
s=[]
ww=0
for i in range(n):
pi,bi=list(map(int,input().split()))
p+=pi-bi
s.append(p)
w=[0 for i in range(p+1)]
for i in range(n):
if s[i]<0:
ww-=s[i]
s[i]=0
elif s[i]>p:
ww+=s[i]-p
s[i]=p
for j in range(p+1):
if j<=s[i]:
w[j]+=s[i]-j
else:
w[j]=min(w[j-1],w[j]+j-s[i])
print(w[p]+ww)
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |