Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
mod=998244353 

N=int(input())
alist=[]
all_num=1
for i in range(N):
  alist.append(int(input()))
  all_num *= 3
  all_num %= mod
  
asum=sum(alist)
#print(alist)
#print(all_num)

dp=[]
dp2=[]
for _ in range(N+1):
  dp.append([0]*(asum+1))
  dp2.append([0]*(asum+1))
  
dp[0][0]=1
dp2[0][0]=1
#print(dp)
for i in range(N):
  a=alist[i]
  for j in range(asum):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    dp2[i+1][j] += dp2[i][j]
    dp2[i+1][j] %= mod
    if dp[i][j] > 0:
      dp[i+1][j+a] += dp[i][j]
      dp[i+1][j+a] %= mod
      dp2[i+1][j+a] += dp2[i][j]
      dp2[i+1][j+a] %= mod
    
#print(dp)
#print(dp2)

invalid_num = sum(dp[N][(asum+1)//2:])%mod 
#print(invalid_num)

if asum%2 == 0:
  print((all_num-3*invalid_num+3*dp2[N][asum//2])%mod)
else:
  print((all_num-3*invalid_num)%mod)

Fixed submission:
mod=998244353 

N=int(input())
alist=[]
all_num=1
for i in range(N):
  alist.append(int(input()))
  all_num *= 3
  all_num %= mod
  
asum=sum(alist)
#print(alist)
#print(all_num)

dp=[]
dp2=[]
for _ in range(N+1):
  dp.append([0]*(asum+1))
  dp2.append([0]*(asum+1))
  
dp[0][0]=1
dp2[0][0]=1
#print(dp)
for i in range(N):
  a=alist[i]
  for j in range(asum):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    dp2[i+1][j] += dp2[i][j]
    dp2[i+1][j] %= mod
    if dp[i][j] > 0:
      dp[i+1][j+a] += dp[i][j]
      dp[i+1][j+a] %= mod
      dp2[i+1][j+a] += dp2[i][j]
      dp2[i+1][j+a] %= mod
    
#print(dp)
#print(dp2)

invalid_num = sum(dp[N][(asum+1)//2:])%mod 
#print(invalid_num)

if asum%2 == 0:
  print((all_num-3*invalid_num+3*dp2[N][asum//2])%mod)
else:
  print((all_num-3*invalid_num)%mod)
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split())
if a <= c and c <= b:
  print(Yes)
elif b <= c and c <= a:
  print(Yes)
else:
  print(No)

Fixed submission:
a,b,c=map(int,input().split())
if a <= c and c <= b:
  print("Yes")
elif b <= c and c <= a:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K = map(int,input().split())
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))
clist = list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)
clist.sort(reverse=True)

ablist = []
for i in alist:
  for j in blist:
      ablist.append(i+j)
      
ablist.sort(reverse=True)
ablist = ablist[0:K]

abclist = []
for ij in ablist:
  for k in clist:
    abclist.append(ij+k)
    
abclist.sort(reverse=True)
for ijk in range(K):
  print(abclist[ijk])

Fixed submission:
X,Y,Z,K = map(int,input().split())
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))
clist = list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)
clist.sort(reverse=True)

ablist = []
for i in alist:
  for j in blist:
      ablist.append(i+j)
      
ablist.sort(reverse=True)
ablist = ablist[0:K]

abclist = []
for ij in ablist:
  for k in clist:
    abclist.append(ij+k)
    
abclist.sort(reverse=True)
for ijk in range(K):
  print(abclist[ijk])
Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
str = input()
for i in range(Q):
  l,r = map(int,input().split())
  substr = str[l-1:r]
  print(substr.count("AC"))

Fixed submission:
N,Q = map(int,input().split())
str = input()
ac_list = [0]
for i in range(1,N):
  if str[i-1:i+1] == "AC":
    ac_list.append(ac_list[-1]+1)
  else:
    ac_list.append(ac_list[-1])
    
for i in range(Q):
  l,r = map(int,input().split())
  print(ac_list[r-1]-ac_list[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cdic={}
for i in range(N2):
  c=c2list[i]
  if not c in cdic:
    cdic[c]=[i]
  else:
    cdic[c].append(i)
#print(cdic)

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  
  for j in reversed(cdic[c]):
    if j<i:
      dp[i]+=dp[j]
      break
    
#print(dp)
print(dp[-1]%MOD)

Fixed submission:
MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cdic={}
for i in range(N2):
  c=c2list[i]
  if not c in cdic:
    cdic[c]=[i]
  else:
    cdic[c].append(i)
#print(cdic)

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  
  if len(cdic[c])<5:
    for j in reversed(cdic[c]):
      if j<i:
        dp[i]+=dp[j]
        break
  else:
    l,r=0,len(cdic[c])
    while(l<=r):
      mid=(l+r)//2
      if cdic[c][mid]<i and cdic[c][mid+1]>=i:
        dp[i]+=dp[cdic[c][mid]]
        break
      elif cdic[c][mid]>=i:
        r=mid-1
      elif cdic[c][mid+1]<i:
        l=mid+1
      else:
        print("error")
    
#print(dp)
print(dp[-1]%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cdic={}
for i in range(N2):
  c=c2list[i]
  if not c in cdic:
    cdic[c]=[i]
  else:
    cdic[c].append(i)
#print(cdic)

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  
  for j in reversed(cdic[c]):
    if j<i:
      dp[i]+=dp[j]
      break
    
#print(dp)
print(dp[-1]%MOD)

Fixed submission:
MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cdic={}
for i in range(N2):
  c=c2list[i]
  if not c in cdic:
    cdic[c]=[i]
  else:
    cdic[c].append(i)
#print(cdic)

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  
  if len(cdic[c])<5:
    for j in reversed(cdic[c]):
      if j<i:
        dp[i]+=dp[j]
        break
  else:
    l,r=0,len(cdic[c])
    while(l<=r):
      mid=(l+r)//2
      if cdic[c][mid]<i and cdic[c][mid+1]>=i:
        dp[i]+=dp[cdic[c][mid]]
        break
      elif cdic[c][mid]>=i:
        r=mid-1
      elif cdic[c][mid+1]<i:
        l=mid+1
      else:
        print("error")
    
#print(dp)
print(dp[-1]%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par = get_par(par_list[x])
    par_list[x] = par
    return par

N,M=map(int,input().split())
edge_list = []
for i in range(M):
  Ai,Bi=map(int,input().split())
  edge_list.append((Ai,Bi))
  
inconv_list_rev = [N*(N-1)//2]
par_list = [i for i in range(N+1)]
for Ai,Bi in reversed(edge_list):
  par_A = get_par(Ai)
  par_B = get_par(Bi)
  if par_A != par_B:
    par_list[par_B] = par_A
    
  cluster_dic = {}
  for par in par_list:
    root = get_par(par)
    if root in cluster_dic:
      cluster_dic[root] += 1
    else:
      cluster_dic[root] = 1
      
  sum_connect = 0
  for key in cluster_dic:
    val = cluster_dic[key]
    sum_connect += val*(val-1)//2
    
  inconv_list_rev.append(N*(N-1)//2-sum_connect)
  
for con in reversed(inconv_list_rev[:-1]):
  print(con)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

N,M=map(int,input().split())
edge_list = []
for i in range(M):
  Ai,Bi=map(int,input().split())
  edge_list.append((Ai,Bi))
  
inconv = N*(N-1)//2
inconv_list_rev = [inconv]
par_list = list(range(N))
size_list = [1]*N
for Ai,Bi in reversed(edge_list):
  par_A = get_par(Ai-1)
  par_B = get_par(Bi-1)
  if par_A != par_B:
    size_A = size_list[par_A]
    size_B = size_list[par_B]
    par_list[par_B] = par_A
    size_list[par_A] += size_list[par_B]        
    inconv -= size_A*size_B
  inconv_list_rev.append(inconv)
    
for con in reversed(inconv_list_rev[:-1]):
  print(con)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import heapq
N,K=map(int,input().split())

hq=[]
tset_all=set()
for i in range(N):
  t,d=map(int,input().split())
  heapq.heappush(hq,(-d,t))
  tset_all.add(t)
#print(heapq)

hq_K=[]
dsum=0
tdic=defaultdict(int)
for i in range(K):
  md,t=heapq.heappop(hq)
  heapq.heappush(hq_K,((-md,t)))
  dsum-=md
  tdic[t]+=1  

t0=len(tdic)
max_answer=dsum+(t0**2)
#print(t0,max_answer)

for i in range(t0+1,len(tset_all)+1):  
  loop_flg=True
  while(loop_flg):
    d,t=heapq.heappop(hq_K)
    if tdic[t]>1:
      tdic[t]-=1
      dsum-=d
      
      while(True):
        md2,t2=heapq.heappop(hq)
        if tdic[t2]==0:
          dsum-=md2
          loop_flg=False
          break
          
  answer_i=dsum+(i**2)
  #print(i,answer_i)
  max_answer=max(max_answer,answer_i)
  
print(max_answer)

Fixed submission:
from collections import defaultdict
import heapq
N,K=map(int,input().split())

hq=[]
tset_all=set()
for i in range(N):
  t,d=map(int,input().split())
  heapq.heappush(hq,(-d,t))
  tset_all.add(t)
#print(heapq)

hq_K=[]
dsum=0
tdic=defaultdict(int)
for i in range(K):
  md,t=heapq.heappop(hq)
  heapq.heappush(hq_K,((-md,t)))
  dsum-=md
  tdic[t]+=1  

t0=len(tdic)
max_answer=dsum+(t0**2)
#print(t0,max_answer)

for i in range(t0+1,min(K,len(tset_all))+1):
  loop_flg=True
  while(loop_flg):
    d,t=heapq.heappop(hq_K)
    if tdic[t]>1:
      tdic[t]-=1
      dsum-=d
      
      while(True):
        md2,t2=heapq.heappop(hq)
        if tdic[t2]==0:
          tdic[t2]=1
          dsum-=md2
          loop_flg=False
          break
          
  answer_i=dsum+(i**2)
  #print(i,answer_i)
  max_answer=max(max_answer,answer_i)
  
print(max_answer)
Buggy python submission (verdict: Runtime Error):
N=int(input())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

ablist=[]
for i in range(N):
  ablist.append(alist[i]-blist[i])
  
ablist.sort()
#print(ablist)

if ablist[0] >= 0:
  print("0")
elif sum(ablist) < 0:
  print("-1")
else:
  cnt = 0
  sum_ab = 0
  for ab in ablist:
    if ab<0:
      cnt += 1
      sum_ab += ab
    else:
      break
      
  for ab in reversed(ablist):
    cnt += 1
    sum_ab += ab
    if sum_ab >= 0:
      break
      
print(cnt)

Fixed submission:
N=int(input())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

ablist=[]
for i in range(N):
  ablist.append(alist[i]-blist[i])
  
ablist.sort()
#print(ablist)

if ablist[0] >= 0:
  print("0")
elif sum(ablist) < 0:
  print("-1")
else:
  cnt = 0
  sum_ab = 0
  for ab in ablist:
    if ab<0:
      cnt += 1
      sum_ab += ab
    else:
      break
      
  for ab in reversed(ablist):
    cnt += 1
    sum_ab += ab
    if sum_ab >= 0:
      break
      
  print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
mod=10**9+7

N,M=map(int,input().split())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)

for i in range(0,N-1):
  if alist[i]==alist[i+1]:
    print(0)
    sys.exit()
for i in range(0,M-1):
  if blist[i]==blist[i+1]:
    print(0)
    sys.exit()

answer=1
cnt_a=0
cnt_b=0
for i in reversed(range(1,N*M+1)):
  if i in alist and i in blist:
    cnt_a+=1
    cnt_b+=1
  elif i in alist:
    cnt_a+=1
    answer*=cnt_b
    answer%=mod
  elif i in blist:
    cnt_b+=1
    answer*=cnt_a
    answer%=mod
  else:
    answer*=(cnt_a*cnt_b-(N*M-i))
    answer%=mod
    
  if answer==0:
    break
    
print(answer)

Fixed submission:
import sys
mod=10**9+7

N,M=map(int,input().split())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)

for i in range(0,N-1):
  if alist[i]==alist[i+1]:
    print(0)
    sys.exit()
for i in range(0,M-1):
  if blist[i]==blist[i+1]:
    print(0)
    sys.exit()

alist.append(0)
blist.append(0)
    
answer=1
cnt_a=0
cnt_b=0
for i in reversed(range(1,N*M+1)):
  if alist[cnt_a]==i and blist[cnt_b]==i:
    cnt_a+=1
    cnt_b+=1
  elif alist[cnt_a]==i:
    cnt_a+=1
    answer*=cnt_b
    answer%=mod
  elif blist[cnt_b]==i:
    cnt_b+=1
    answer*=cnt_a
    answer%=mod
  else:
    answer*=(cnt_a*cnt_b-(N*M-i))
    answer%=mod
    
  if answer==0:
    break
    
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())

mat=[[x=="#" for x in input()] for _ in range(H)]
#print(mat)

answer=0
for i in range(H):
  for j in range(W):
    if not mat[i][j]:
      continue
      
    visited_set=set()
    queue=[(i,j)]
    d=0
    while queue:
      new_queue=set()
      for q in queue:
        ii,jj=q
        visited_set.add((ii,jj))
        if d%2==1:
          answer+=1
        
        if ii>0 and mat[ii][jj]!=mat[ii-1][jj] and not (ii-1,jj) in visited_set:
          new_queue.add((ii-1,jj))
        if ii<H-1 and mat[ii][jj]!=mat[ii+1][jj] and not (ii+1,jj) in visited_set:
          new_queue.add((ii+1,jj))
        if jj>0 and mat[ii][jj]!=mat[ii][jj-1] and not (ii,jj-1) in visited_set:
          new_queue.add((ii,jj-1))
        if jj<W-1 and mat[ii][jj]!=mat[ii][jj+1] and not (ii,jj+1) in visited_set:
          new_queue.add((ii,jj+1))
          
      queue=list(new_queue)
      d+=1

print(answer)

Fixed submission:
H,W=map(int,input().split())

mat=[[x=="#" for x in input()] for _ in range(H)]
#print(mat)

answer=0
visited_set=set()
for i in range(H):
  for j in range(W):
    if not mat[i][j] or (i,j) in visited_set:
      continue      

    queue=[(i,j)]
    d=0
    num_black=num_white=0
    while queue:
      new_queue=set()
      for q in queue:
        ii,jj=q
        visited_set.add((ii,jj))
        if d%2==0:
          num_black+=1
        else:
          num_white+=1
        
        if ii>0 and mat[ii][jj]!=mat[ii-1][jj] and not (ii-1,jj) in visited_set:
          new_queue.add((ii-1,jj))
        if ii<H-1 and mat[ii][jj]!=mat[ii+1][jj] and not (ii+1,jj) in visited_set:
          new_queue.add((ii+1,jj))
        if jj>0 and mat[ii][jj]!=mat[ii][jj-1] and not (ii,jj-1) in visited_set:
          new_queue.add((ii,jj-1))
        if jj<W-1 and mat[ii][jj]!=mat[ii][jj+1] and not (ii,jj+1) in visited_set:
          new_queue.add((ii,jj+1))
          
      queue=list(new_queue)
      d+=1
      
    #print(i,j,num_black,num_white)
    answer+=num_black*num_white

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
alist=list(map(int,input().split()))

sum_list=[]
for i in range(N):
  s=0
  for j in range(i,N):
    s+=alist[j]
    sum_list.append(s)
    
sum_list.sort(reverse=True)
#print(sum_list)

answer=0
for i in reversed(range(41)):
  x=2**i
  cnt=0
  for s in sum_list:
    if (answer+x)&s==answer+x:
      cnt+=1
      if cnt>=K:
        answer+=x
        break
  
print(answer)

Fixed submission:
N,K=map(int,input().split())
alist=list(map(int,input().split()))

sum_list=[]
for i in range(N):
  s=0
  for j in range(i,N):
    s+=alist[j]
    sum_list.append(s)
    
sum_list.sort(reverse=True)
#print(sum_list)

answer=0
for i in reversed(range(41)):
  x=2**i
  cnt=0
  for s in sum_list:
    if answer+x>s:
      break
    elif (answer+x)&s==answer+x:
      cnt+=1
      if cnt>=K:
        answer+=x
        break
  
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N,M,Q=map(int,input().split())

xmat,cmat=[],[]
for i in range(N+1):
  xmat.append([0]*(N+1))
  cmat.append([0]*(N+1))

for i in range(M):
  l,r=map(int,input().split())
  xmat[l][r]+=1
#print(xmat)

for i in range(1,N+1):
  for j in range(1,N+1):
    cmat[i][j]=xmat[i][j]+cmat[i][j-1]
#print(cmat)

for i in range(Q):
  p,q=map(int,input().split())
  ans=0
  for k in range(p,q+1):
    ans+=cmat[k][q]-cmat[k][p-1]
  print(ans)

Fixed submission:
N,M,Q=map(int,input().split())

xmat,cmat=[],[]
for i in range(N+1):
  xmat.append([0]*(N+1))
  cmat.append([0]*(N+1))

for i in range(M):
  l,r=map(int,input().split())
  xmat[l][r]+=1
#print(xmat)

for i in range(1,N+1):
  for j in range(1,N+1):
    cmat[i][j]=xmat[i][j]+cmat[i][j-1]
#print(cmat)

for i in range(Q):
  p,q=map(int,input().split())
  ans=0
  for k in range(p,q+1):
    ans+=cmat[k][q]-cmat[k][p-1]
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
alist=list(map(int,input().split()))

def bs_left(mid,mp):
  sum2=abs(2*slist[mid]-slist[mp])
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*slist[mid-1]-slist[mp])
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*slist[mid+1]-slist[mp])

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    

def bs_right(mid,mp):
  sum2=abs(2*(slist[mid]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*(slist[mid-1]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*(slist[mid+1]-slist[mp])-(slist[-1]-slist[mp]))

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    
  
slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)
#print(alist)
#print(slist)

dic_lp,dic_rp={},{}
for mp in range(1,N-2):  
  #lp
  l,r=0,mp
  while(l<=r):
    mid=(l+r)//2
    ret=bs_left(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_lp[mp]=mid
      #print(mp,mid)
      break
  
  #rp
  l,r=mp+1,N-2
  while(l<=r):
    mid=(l+r)//2
    ret=bs_right(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_rp[mp]=mid
      #print(mp,mid)
      break
    
min_diff=10**9
for mp in range(1,N-2):
  lp=dic_lp[mp]
  rp=dic_rp[mp]
  
  sum1=slist[lp]
  sum2=slist[mp]-slist[lp]
  sum3=slist[rp]-slist[mp]
  sum4=slist[-1]-slist[rp]
  #print(sum1,sum2,sum3,sum4)
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  #print(lp,mp,rp,diff)
  if diff<min_diff:
    min_diff=diff    
  
print(min_diff)

Fixed submission:
N=int(input())
alist=list(map(int,input().split()))

slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)
#print(alist)
#print(slist)

dic_lp,dic_rp={},{}
lp,rp=0,2
for mp in range(1,N-2):
  #p1
  mindiff=slist[mp]
  while(lp<mp+1):
    sum1=slist[lp]
    sum2=slist[mp]-slist[lp]
    
    diff=abs(sum1-sum2)
    if mindiff>diff:
      lp+=1
      mindiff=diff
    else:
      lp-=1
      dic_lp[mp]=lp
      #print(mp,lp)
      break
    
  rp=max(rp,mp+1)
  mindiff=slist[-1]-slist[mp]
  while(rp<N):
    sum1=slist[-1]-slist[rp]
    sum2=slist[rp]-slist[mp]
    
    diff=abs(sum1-sum2)
    if mindiff>diff:
      rp+=1
      mindiff=diff
    else:
      rp-=1
      dic_rp[mp]=rp
      #print(mp,rp)
      break
    
min_diff=10**9
for mp in range(1,N-2):
  lp=dic_lp[mp]
  rp=dic_rp[mp]
  
  sum1=slist[lp]
  sum2=slist[mp]-slist[lp]
  sum3=slist[rp]-slist[mp]
  sum4=slist[-1]-slist[rp]
  #print(sum1,sum2,sum3,sum4)
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  #print(lp,mp,rp,diff)
  if diff<min_diff:
    min_diff=diff
    #print(min_diff)
  
print(min_diff)
Buggy python submission (verdict: Runtime Error):
N=int(input())

max_answer=0
for k in range(101):
  answer=0
  k1=k
  k2=100-k

  red_list=[]
  for i in range(N):
    a,b=map(int,input().split())
    red_list.append((k1*a+k2*b,a,b))
  red_list.sort()

  blue_list=[]
  for i in range(N):
    c,d=map(int,input().split())
    blue_list.append((k1*c+k2*d,c,d))
  blue_list.sort()

  #print(red_list)
  #print(blue_list)

  answer=0
  selected_set=set()
  for i in range(N):
    rs,rx,ry=red_list[i]
    for j in range(N):
      if j in selected_set:
        continue
      bs,bx,by=blue_list[j]
      if rx<bx and ry<by:
        #print((rx,ry),(bx,by))
        selected_set.add(j)
        answer+=1
        break
      
  max_answer=max(max_answer,answer)
  
print(max_answer)


Fixed submission:
N=int(input())

red_list=[]
for i in range(N):
  a,b=map(int,input().split())
  red_list.append((a,b))
red_list.sort()
  
blue_list=[]
for i in range(N):
  c,d=map(int,input().split())
  blue_list.append((c,d))
blue_list.sort()

#print(red_list)
#print(blue_list)

answer=0
selected_set=set()
for i in range(N):
  c,d=blue_list[i]
  max_y=-1
  maxarg_y=-1
  for j in range(N):
    a,b=red_list[j]
    if c<=a:
      break
    
    if b<d and b>max_y and not j in selected_set:
      max_y=b
      maxarg_y=j
      
  if maxarg_y!=-1:
    answer+=1    
    selected_set.add(maxarg_y)
    #print(red_list[maxarg_y],blue_list[i])
    
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

sdic={}
t=0
while(t<=tsum):
  s=10**9
  for con in const_list:
    l,r,v=con
    s=min(s,const(l,r,v,t))  
  sdic[t]=s
  t+=0.5

answer=0
t=0
while(t<tsum):
  answer+=(sdic[t]+sdic[t+0.5])*0.5/2
  t+=0.5
  
print(answer)

Fixed submission:
N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

answer=0
t=0
while(t<tsum):
  s1=s2=10**9
  for con in const_list:
    l,r,v=con
    s1=min(s1,const(l,r,v,t))
    s2=min(s2,const(l,r,v,t+0.5))
  #print(s1,s2)
    
  answer+=(s1+s2)*0.5/2
  t+=0.5
  
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

answer=0
t=0
while(t<tsum):
  s1=s2=10**9
  for con in const_list:
    l,r,v=con
    s1=min(s1,const(l,r,v,t))
    s2=min(s2,const(l,r,v,t+0.5))
  #print(s1,s2)
    
  answer+=(s1+s2)*0.5/2
  t+=0.5
  
print(answer)

Fixed submission:
N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

answer=0
t=0
while(t<tsum):
  s1=s2=10**9
  for con in const_list:
    l,r,v=con
    s1=min(s1,const(l,r,v,t))
    s2=min(s2,const(l,r,v,t+0.5))
  #print(s1,s2)
    
  answer+=(s1+s2)*0.5/2
  t+=0.5
  
print(answer)