TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
H,W = list(map(int,input().split()))

ans = float('inf')
a,b,c = H//3*W,(H-H//3)*(W//2),(H-H//3)*(W-W//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = (H+2)//3*W,(H-(H+2)//3)*(W//2),(H-(H+2)//3)*(W-W//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = W//3*H,(W-W//3)*(H//2),(W-W//3)*(H-H//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = (W+2)//3*H,(W-(W+2)//3)*(H//2),(W-(W+2)//3)*(H-H//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = H//3*W,H//3*W,(H//3+1)*W
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = W//3*H,W//3*H,(W//3+1)*H
ans = min(ans,max(a,b,c)-min(a,b,c))

print(ans)

H,W = list(map(int,input().split()))

ans = float('inf')
a,b,c = H//3*W,(H-H//3)*(W//2),(H-H//3)*(W-W//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = (H+2)//3*W,(H-(H+2)//3)*(W//2),(H-(H+2)//3)*(W-W//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = W//3*H,(W-W//3)*(H//2),(W-W//3)*(H-H//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = (W+2)//3*H,(W-(W+2)//3)*(H//2),(W-(W+2)//3)*(H-H//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = H//3*W,H//3*W,((H+2)//3)*W
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = W//3*H,W//3*H,((W+2)//3)*H
ans = min(ans,max(a,b,c)-min(a,b,c))

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
H,W = map(int,input().split())
def f(H,W):
    # if H%3 == 0:
    #     return 0
    w = W//2
    res = H*W
    for h in range(1,H):
        sb = (H-h)*w
        sc = (H-h)*(W-w)
        sa = h*W
        res = min(res, max(sa,sb,sc) - min(sa,sb,sc))
    return res
ans = min(f(H,W), f(W,H))
print(ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,W = map(int,read().split())

def F(H,W):
    opt = H * W + 100
    for a in range(1,W):
        x = H * a
        y = (W-a) * (H//2)
        z = (W-a) * (H-H//2)
        d = max(x,y,z) - min(x,y,z)
        if opt > d:
            opt = d
    if W >= 3:
        a = W//3
        b = (W-a)//2
        c = W-a-b
        d = (max(a,b,c) - min(a,b,c)) * H
        if opt > d:
            opt = d
    return opt

answer = min(F(H,W),F(W,H))
print(answer)


Verdicts: Wrong Answer

Accepted
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    heapq.heappop(P)
    sp = sum(P)
    p[i] = sum(Q)
for i in range(1,N+1):
    heapq.heappush(Q,-R[-i])
    heapq.heappop(Q)
    sq = sum(Q)
    q[i] = sq

ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)


N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    x = heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    y = heapq.heappop(Q)
    sp = sp + R[i-1] - x
    sq = sq - R[-i] - y
    p[i] = sp
    q[i] = sq
ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)


W,H = map(int,input().split())
ans = 10**30
for i in range(1,W):
    a = H*i
    w = W - i
    b = max((w//2)*H,w*(H//2))
    c = w*H - b
    x = max(a,b,c) - min(a,b,c)
    ans = min(ans,x)
for i in range(1,H):
    a = W*i
    h = H - i
    b = max((W//2)*h,W*(h//2))
    c = h*W - b
    x = max(a,b,c) - min(a,b,c)
    ans = min(ans,x)
print(ans)

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
if H%3==0 or W%3==0:
    answer = 0
else:
    answer = min(H, W)

def cal(H, W):
    h = H // 3
    area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
    answer = min(answer, max(area)-min(area))
    h += 1
    area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
    answer = min(answer, max(area)-min(area))

cal(H, W)
cal(W, H)
print(answer)
# 13

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
if H%3==0 or W%3==0:
    answer = 0
else:
    answer = min(H, W)

def cal(H, W):
    global answer
    h = H // 3
    area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
    answer = min(answer, max(area)-min(area))
    h += 1
    area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
    answer = min(answer, max(area)-min(area))

cal(H, W)
cal(W, H)
print(answer)
# 13

Verdicts: Runtime Error

Accepted
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def diff_min(L):
    len_L = len(L)
    ret = min([abs(L[i] - L[(i+1)%len_L]) for i in range(len_L)])
    return ret

def resolve():
    H, W = LI()

    ans = 0
    if H % 3 != 0 and W % 3 != 0:
        
        ans = min(H, W)

        
        s = [0] * 3
        
        for _ in range(2):
            s[0] = H * W // 3
            s[1] = (H * W - s[0]) // 2
            s[2] = (H * W - s[0]) - s[1]
            ans = min(diff_min(s), ans)
            s[0] = H * (W // 3 + 1)
            s[1] = (H * W - s[0]) // 2
            s[2] = (H * W - s[0]) - s[1]
            ans = min(diff_min(s), ans)
            H, W = W, H
       
    print(ans)

    print(ans)

if __name__ == '__main__':
    resolve()


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()

    ans = INF
    if H % 3 == 0 or W % 3 == 0:
        ans = 0
    else:
        
        ans = min(H, W)

        
        s = [0] * 3
        
        for _ in range(2):
            s[0] = H * (W // 3)
            s[1] = (W - W // 3) * (H // 2)
            s[2] = (W - W // 3) * (H - H // 2)
            ans = min(max(s)- min(s), ans)
            s[0] = H * (W // 3 + 1)
            s[1] = (W - (W // 3 + 1)) * (H // 2)
            s[2] = (W - (W // 3 + 1)) * (H - H // 2)
            ans = min(max(s)- min(s), ans)
            H, W = W, H
       
    print(ans)

if __name__ == '__main__':
    resolve()


Verdicts: Wrong Answer

Accepted
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
temp=input().split()
H=int(temp[0])
W=int(temp[1])

INF=100000000

ans=INF

if H%3==0 or W%3==0:
	print(0)
if H%2==0:
	for i in range(W):
		S1=H*i
		S2=int(H/2)*(W-i)
		if abs(S1-S2)<ans:
			ans=abs(S1-S2)
if W%2==0:
	ans=INF
	for i in range(H):
		S1=W*i
		S2=int(W/2)*(H-i)
		if abs(S1-S2)<ans:
			ans=min(ans,abs(S1-S2))
			
for i in range(H):
	for j in range(W):
		
		S1=W*i
		S2=j*(H-i)
		S3=(W-j)*(H-i)
		minS=min(S1,S2,S3)
		maxS=max(S1,S2,S3)
		if maxS-minS<ans:
			ans=maxS-minS
		
		S1=H*j
		S2=i*(W-j)
		S3=(H-i)*(W-j)
		minS=min(S1,S2,S3)
		maxS=max(S1,S2,S3)
		if maxS-minS<ans:
			ans=maxS-minS

ans=min(ans,H,W)

	
	
print(ans)
	

temp=input().split()
H=int(temp[0])
W=int(temp[1])

INF=10000000000
ans=INF

if H%3==0 or W%3==0:
	ans=0
ans=min(ans,H,W)

for i in range(H):
	S1=W*i
	S2=int(W/2)*(H-i)
	S3=(W-int(W/2))*(H-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
for i in range(W):
	S1=H*i
	S2=int(H/2)*(W-i)
	S3=(H-int(H/2))*(W-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
import math
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
  exit(0)
S=[0]*3
s=H*import math
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
  exit(0)
S=[0]*3
s=H*W/3
w0=math.ceil(s/H)
h0=math.ceil(s/W)

S[0]=w0*H
w1=W-W/3
w0=math.ceil(s/H)
h0=math.ceil(s/W)

S[0]=w0*H
w1=W-w0
if w1%2==0 or H%2==0:
  S[1]=(H*w1)//2
  S[2]=(H*w1)//2
else:
  s1=H*w1/2
  w10=math.ceil(s1/H)
  h10=math.ceil(s1/w1)
  S[2]=max((w1-w10)*H,(H-h10)*w1)
ans=abs(S[0]-S[2])

S[0]=W*h0
h1=H-h0
if h1%2==0 or W%2==0:
  S[1]=(W*h1)//2
  S[2]=(W*h1)//2
else:
  s1=h1*W/2
  w11=math.ceil(s1/h1)
  h11=math.ceil(s1/W)
  S[2]=max((W-w11)*h1,(h1-h11)*W)
ans=min(ans,abs(S[0]-S[2]))


S=[0]*3
s=H*W/3
w0=math.floor(s/H)
h0=math.floor(s/W)

S[0]=w0*H
w1=W-w0
if w1%2==0 or H%2==0:
  S[1]=(H*w1)//2
  S[2]=(H*w1)//2
else:
  s1=H*w1/2
  w10=math.floor(s1/H)
  h10=math.floor(s1/w1)
  S[2]=max((w1-w10)*H,(H-h10)*w1)
ans=min(ans,abs(S[0]-S[2]))

S[0]=W*h0
h1=H-h0
if h1%2==0 or W%2==0:
  S[1]=(W*h1)//2
  S[2]=(W*h1)//2
else:
  s1=h1*W/2
  w11=math.floor(s1/h1)
  h11=math.floor(s1/W)
  S[2]=max((W-w11)*h1,(h1-h11)*W)
ans=min(ans,abs(S[0]-S[2]))

print(ans)

import math
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
  exit(0)
S=[0]*3
s=H*W/3
w0=math.ceil(s/H)
h0=math.ceil(s/W)

S[0]=w0*H
w1=W-W/3
w0=math.ceil(s/H)
h0=math.ceil(s/W)

S[0]=w0*H
w1=W-w0
if w1%2==0 or H%2==0:
  S[1]=(H*w1)//2
  S[2]=(H*w1)//2
else:
  s1=H*w1/2
  w10=math.ceil(s1/H)
  h10=math.ceil(s1/w1)
  S[2]=max((w1-w10)*H,(H-h10)*w1)
ans=abs(S[0]-S[2])

S[0]=W*h0
h1=H-h0
if h1%2==0 or W%2==0:
  S[1]=(W*h1)//2
  S[2]=(W*h1)//2
else:
  s1=h1*W/2
  w11=math.ceil(s1/h1)
  h11=math.ceil(s1/W)
  S[2]=max((W-w11)*h1,(h1-h11)*W)
ans=min(ans,abs(S[0]-S[2]))


S=[0]*3
s=H*W/3
w0=math.floor(s/H)
h0=math.floor(s/W)

S[0]=w0*H
w1=W-w0
if w1%2==0 or H%2==0:
  S[1]=(H*w1)//2
  S[2]=(H*w1)//2
else:
  s1=H*w1/2
  w10=math.floor(s1/H)
  h10=math.floor(s1/w1)
  S[2]=max((w1-w10)*H,(H-h10)*w1)
ans=min(ans,abs(S[0]-S[2]))

S[0]=W*h0
h1=H-h0
if h1%2==0 or W%2==0:
  S[1]=(W*h1)//2
  S[2]=(W*h1)//2
else:
  s1=h1*W/2
  w11=math.floor(s1/h1)
  h11=math.floor(s1/W)
  S[2]=max((W-w11)*h1,(h1-h11)*W)
ans=min(ans,abs(S[0]-S[2]))

print(ans)

Verdicts: Runtime Error

Accepted
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
H, W = [int(i) for i in input().split()]


if H%3==0 or W%3==0:
    print(0)

mind = 10**18

for h in range(H+1):
    a = [W*h]
    a.append((W//2)*(H-h))
    a.append(((W//2)+(1 if W%2 else 0))*(H-h))
    mind = min(mind, max(a)-min(a))

for w in range(W+1):
    a = [w*H]
    a.append((W-w)*(H//2))
    a.append((W-w)*((H//2)+(1 if H%2 else 0)))
    mind = min(mind, max(a)-min(a))

print(mind)

H, W = [int(i) for i in input().split()]


if H%3==0 or W%3==0:
    print(0)
    quit()

mind = 10**18

for h in range(H+1):
    a = [W*h]
    if W%2==0 or (H-h)%2==0:
        a.append(int(W/2*(H-h)))
    else:
        a.append(W*(H-h)-min(H-h, W)*(max(H-h, W)//2))
        a.append(W*(H-h)-a[-1])
    mind = min(mind, max(a)-min(a))


for w in range(W+1):
    a = [w*H]
    if (W-w)%2==0 or H%2==0:
        a.append(int((W-w)/2*H))
    else:
        a.append((W-w)*H-min(W-w, H)*(max(W-w, h)//2))
        a.append((W-w)*h-a[-1])
    mind = min(mind, max(a)-min(a))

print(mind)

Verdicts: Wrong Answer

Accepted
Problem: There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.  Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} \- S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Submission attempts (in order):
n = int(input())
array = [int(i) for i in input().split()]
ans=-1e14

for i in range(n, 2*n+1):
    l_array = sorted(array[:i])
    r_array = sorted(array[i:])
    ans = max(ans, sum(l_array[i-n:])-sum(r_array[:n]))

print(ans)

h,w = [int(i) for i in input().split()]

def solve(h,w):
    ans = min(h,w)
    for i in range(1,h):
        p1 = w*i
        p2 = (h-i)*(w//2)
        p3 = h*w-p1-p2
        ans = min(ans, max(p1,p2,p3)-min(p1,p2,p3))
    return ans 

ans = min(solve(h,w), solve(w,h))
if h*w % 3 == 0:
    ans = 0

print(ans)

Verdicts: Runtime Error

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import heapq
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n+1):
  m=0
  b1=a[:n+i]
  b2=a[n+i:]
  heapq.heapify(b1)
  heapq.heapify(b2)
  for j in range(i):
    b=heapq.heappop(b1)
  for j in range(n-i):
    b=heapq.heappop(b2)
  m=sum(b1)-sum(b2)
  if ans<m or i==0:
    ans=m
print(ans)

import heapq
n=int(input())
a=list(map(int,input().split()))
ans=[0 for i in range(n+1)]
ans[0]=sum(a[:n])
b=a[:n]
heapq.heapify(b)
sb=sum(b)
for i in range(n):
  sb+=a[n+i]
  c=heapq.heappushpop(b,a[n+i])
  sb-=c
  ans[i+1]=sb
b=a[2*n:]
for i in range(n):
  b[i]=-b[i]
heapq.heapify(b)
ans[n]+=sum(b)
sb=sum(b)
for i in range(n-1,-1,-1):
  sb-=a[n+i]
  c=heapq.heappushpop(b,-a[n+i])
  sb-=c
  ans[i]+=sb
print(max(ans))

Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import heapq
n = int(input())
a = list(map(int, input().split()))

l = a[:n]
heapq.heapify(l)
memo_l = [0 for _ in range(n+1)]
memo_l[0] = sum(a[:n])

for i in range(1, n+1):
    memo_l[i] = memo_l[i-1]
    if l[0] < a[n+i-1]:
        x = heapq.heappop(l)
        heapq.heappush(l, a[n+i-1])
        memo_l[i] += a[n+i-1] - x


r = [-a[-i] for i in range(1, n+1)]
heapq.heapify(r)
memo_r = [0 for _ in range(n+1)]
memo_r[0] = sum(a[-n:])

for i in range(1, n+1):
    memo_r[i] = memo_r[i-1]
    if abs(x) > a[-n-i]:
        x = heapq.heappop(r)
        heapq.heappush(r, -a[-n-i])
        memo_r[i] += x + a[-n-i]


ans = - 10 ** 20
for i in range(n+1):
    ans = max(ans, memo_l[i] - memo_r[n-i])

print(ans)

import heapq
n = int(input())
a = list(map(int, input().split()))

l = a[:n]
heapq.heapify(l)
memo_l = [0 for _ in range(n+1)]
memo_l[0] = sum(a[:n])

for i in range(1, n+1):
    memo_l[i] = memo_l[i-1]
    if l[0] < a[n+i-1]:
        x = heapq.heappop(l)
        heapq.heappush(l, a[n+i-1])
        memo_l[i] += a[n+i-1] - x


r = [-a[-i] for i in range(1, n+1)]
heapq.heapify(r)
memo_r = [0 for _ in range(n+1)]
memo_r[0] = sum(a[-n:])

for i in range(1, n+1):
    memo_r[i] = memo_r[i-1]
    if abs(r[0]) > a[-n-i]:
        x = heapq.heappop(r)
        heapq.heappush(r, -a[-n-i])
        memo_r[i] += x + a[-n-i]


ans = - 10 ** 20
for i in range(n+1):
    ans = max(ans, memo_l[i] - memo_r[n-i])

print(ans)

Verdicts: Runtime Error

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import heapq
N = int(input())
a = list(map(int, input().split()))

max_result = -1000000

for k in range(N, 2*N+1):
  print("----------------")
  big_a = a[:k]
  heapq.heapify(big_a)
  print(big_a)
  small_a =[(-x, x) for x in a[k:]]
  heapq.heapify(small_a)
  print(small_a)

  for i in range(len(big_a) - N):
    heapq.heappop(big_a)
  print(big_a)

  for i in range(len(small_a) - N):
    heapq.heappop(small_a)
  print(small_a)

  big_sum = sum(big_a)
  small_sum = 0
  for i in small_a:
    small_sum += i[1]

  if (big_sum - small_sum) > max_result:
    max_result = big_sum - small_sum

print(max_result)



import heapq
N = int(input())
a = list(map(int, input().split()))

max_result = -1000000

big_a = a[:N]
big_sum = [sum(big_a)]
heapq.heapify(big_a)
for i in range(N):
  heapq.heappush(big_a, a[N+i])
  p = heapq.heappop(big_a)
  big_sum.append(big_sum[-1] + a[N+i] - p)

small_a = [-i for i in a[-N:]]
small_sum = [sum(small_a)]
heapq.heapify(small_a)
for i in range(N):
  heapq.heappush(small_a, -a[-N-i-1])
  p = heapq.heappop(small_a)
  small_sum.append(small_sum[-1] - a[-N-i-1] - p)

max_result = -float('inf')

for m,s in zip(big_sum, small_sum[::-1]):
  max_result = max(m + s, max_result)

print(max_result)



Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import sys
import heapq


def solve(n, a):
    res = -10 ** 20
    for i in range(n, 2 * n + 1):
        l = a[0:i]
        r = a[i:3 * n]
        l.sort(reverse=True)
        r.sort()
        res0 = sum(l[0:n]) - sum(r[0:n])
        if res0 > res:
            res = res0
    return res


def find_best(n, a):
    h = list()
    s = 0
    best_s = 0
    res = list()
    for i in range(0, 2 * n):
        heapq.heappush(h, a[i])
        s += a[i]
        if len(h) > n:
            m = heapq.heappop(h)
            s -= m
        if len(h) == n:
            if best_s < s:
                best_s = s
            res.append(best_s)
    return res


def solve_large(n, a):
    res = -10 ** 20
    max_l = find_best(n, a)
    b = [-x for x in reversed(a)]
    max_r = find_best(n, b)
    max_r.reverse()
    for l, r in zip(max_l, max_r):
        res0 = l + r
        if res < res0:
            res = res0
    return res



n = int(input())
a = list(map(int, input().split()))
print(solve_large(n, a))


import os
import sys
import heapq


def solve(n, a):
    res = -10 ** 20
    for i in range(n, 2 * n + 1):
        l = a[0:i]
        r = a[i:3 * n]
        l.sort(reverse=True)
        r.sort()
        res0 = sum(l[0:n]) - sum(r[0:n])
        if res0 > res:
            res = res0
    return res


def find_best(n, a):
    h = list()
    s = 0
    best_s = -10**20
    res = list()
    for i in range(0, 2 * n):
        heapq.heappush(h, a[i])
        s += a[i]
        if len(h) > n:
            m = heapq.heappop(h)
            s -= m
        if len(h) == n:
            if best_s < s:
                best_s = s
            res.append(best_s)
    return res


def solve_large(n, a):
    res = -10 ** 20
    max_l = find_best(n, a)
    b = [-x for x in reversed(a)]
    max_r = find_best(n, b)
    max_r.reverse()
    for l, r in zip(max_l, max_r):
        res0 = l + r
        if res < res0:
            res = res0
    return res


input_file = 'd1.in'
if os.path.exists(input_file):
    sys.stdin = open(input_file)
n = int(input())
a = list(map(int, input().split()))
print(solve_large(n, a))


Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) 
  heapq.heappush(R,-A[-1-i]) 
  
#print(L,R,C)

lp = 0 
rp = 0
for i in range(N):
  #print(i,lp,rp)
  if C[lp] - L[0] >= -C[-1-rp] - R[0]: 
    heapq.heappush(L, C[lp]) 
    temp = heapq.heappop(L)
    lp += 1
  else:
    heapq.heappush(R, -C[-1-rp])
    temp = heapq.heappop(R)    
    rp += 1
print(L,R,lp,rp)
ans = sum(L) + sum(R)
print(ans)
    

import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) 
  heapq.heappush(R,-A[-1-i]) 


ansL = [sum(L)]
for i in range(N):
  heapq.heappush(L,C[i])
  rmv = heapq.heappop(L)
  temp = ansL[i] + C[i] - rmv 
  ansL.append(temp)
  

ansR = [sum(R)]
for i in range(N):
  heapq.heappush(R,-C[-1-i])
  rmv = heapq.heappop(R)
  temp = ansR[i] - C[-1-i] - rmv
  ansR.append(temp)
  

ans = -float('inf')
for i in range(N+1):
  temp = ansL[i]+ansR[-1-i]
  ans = max(ans,temp)
#print(ansL,ansR)
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 18:58:46 2020

@author: naoki
"""
from heapq import heappush, heappop
import sys

N = int(input())
a = list(map(int,input().split()))

hq = []
hq_r = []
for i in range(N):
    heappush(hq,a[i])
    heappush(hq_r,-1*a[-1-i])


max_A = [0 for _ in range(N+1)]
max_A[0] = sum(hq)

min_C = [0 for _ in range(N+1)]
min_C[0] = sum(hq_r) * (-1)

for i in range(N):
    heappush(hq, a[N+i])
    heappush(hq_r, -1*a[-N-1-i])
    minus = heappop(hq)
    minus_r = heappop(hq_r)
    max_A[i+1] = max_A[i] + a[N+i] - minus
    min_C[i+1] = min_C[i] + a[-N-1-i] + minus_r
    
max_val = -10e+100
print(max_val)
for i in range(N+1):
    kari = max_A[i] - min_C[-1-i]
    if max_val < kari:
        max_val =kari
print(max_val)



N = int(input())
a = list(map(int, input().split()))

A = (a[0:N])
A = deque(sorted(A))
B = deque(a[N:2*N])
C = a[2*N:3*N]
C = deque(sorted(C, reverse = True))

original_score = 0
for i in range(N):
    original_score += A[i] - C[i]

left = 0
right = 0

for i in range(N):
    left_candidate = B[left] - A[left]
    right_candidate = C[right] - B[-1-right]
    
    if left_candidate >= right_candidate:
        left+=1
        original_score+=left_candidate
    else:
        right+=1
        original_score+=right_candidate
print(original_score)

# -*- coding: utf-8 -*-
"""
Created on Sun May  3 18:58:46 2020

@author: naoki
"""
from heapq import heappush, heappop
import sys

N = int(input())
a = list(map(int,input().split()))

hq = []
hq_r = []
for i in range(N):
    heappush(hq,a[i])
    heappush(hq_r,-1*a[-1-i])


max_A = [0 for _ in range(N+1)]
max_A[0] = sum(hq)

min_C = [0 for _ in range(N+1)]
min_C[0] = sum(hq_r) * (-1)

for i in range(N):
    heappush(hq, a[N+i])
    heappush(hq_r, -1*a[-N-1-i])
    minus = heappop(hq)
    minus_r = heappop(hq_r)
    max_A[i+1] = max_A[i] + a[N+i] - minus
    min_C[i+1] = min_C[i] + a[-N-1-i] + minus_r
    
max_val = -10e+100
for i in range(N+1):
    kari = max_A[i] - min_C[-1-i]
    if max_val < kari:
        max_val =kari
print(max_val)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
from heapq import heappush, heappop
n=int(input())
a=list(map(int, input().split()))
q1=[]
q2=[]
s1=[]
s2=[]
for i in range(n):
    heappush(q1, a[i])
s1.append(sum(a[0:n]))
for ai in a[n:2*n]:
    heappush(q1, ai)
    m=heappop(q1)
    s1.append(s1[-1]+ai-m)
a=a[::-1]
for i in range(n):
    heappush(q2, -a[i])
s2.append(-sum(a[0:n]))
for ai in [-i for i in a[n:2*n]]:
    heappush(q2, ai)
    m=heappop(q2)
    s2.append(s2[-1]+ai-m)
ans=-1
print(s1, s2)
for i in range(n+1):
    ans=max(s1[i]+s2[-i-1], ans)
print(ans) 

from heapq import heappush, heappop
n=int(input())
a=list(map(int, input().split()))
q1=[]
q2=[]
s1=[]
s2=[]
for i in range(n):
    heappush(q1, a[i])
s1.append(sum(a[0:n]))
for ai in a[n:2*n]:
    heappush(q1, ai)
    m=heappop(q1)
    s1.append(s1[-1]+ai-m)
a=a[::-1]
for i in range(n):
    heappush(q2, -a[i])
s2.append(-sum(a[0:n]))
for ai in [-i for i in a[n:2*n]]:
    heappush(q2, ai)
    m=heappop(q2)
    s2.append(s2[-1]+ai-m)
ans=s1[0]+s2[-1]
for i in range(n+1):
    ans=max(s1[i]+s2[-i-1], ans)
print(ans)    

Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
def f(a):q=a[:n];heapify(q);return sum(q)+cumsum([e-heappushpop(q,e)for e in a[n:n-~n]]);from heapq import*;from numpy import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),f([-e for e in a[::-1]])[::-1]))))

def f(a):
	q=a[:n];s=sum(q);heapify(q)
	for e in a[n:2*n]:yield s;s+=e-heappushpop(q,e)
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))

def f(a):q=a[:n];heapify(q);return sum(q)+cumsum([e-heappushpop(q,e)for e in a[n:n-~n]])
from heapq import*;from numpy import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),f([-e for e in a[::-1]])[::-1]))))

def f(a):
	q=a[:n];s=sum(q);heapify(q);yield s
	for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))

Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import heapq
N = int(input())
A = list(map(int, input().split()))
R = [a for a in A[:N]]
M = [a for a in A[N:2*N]]
B = [-a for a in A[2*N:3*N]]
res_R = [0] * (N + 1)
res_B = [0] * (N + 1)
res_R[0] = sum(R)
res_B[N] = -sum(B)
heapq.heapify(R)
heapq.heapify(B)
for i in range(N):
    heapq.heappush(R, M[i])
    a = heapq.heappop(R)
    res_R[i+1] = res_R[i] + M[i] - a
    heapq.heappush(B, -M[N-i-1])
    a = heapq.heappop(B)
    res_B[N-i-1] = res_B[N-i] + M[N-i-1] + a
print(max(r - b for r, b in zip(res_R, res_B)))
print(res_R)
print(res_B)

import heapq
N = int(input())
A = list(map(int, input().split()))
R = [a for a in A[:N]]
M = [a for a in A[N:2*N]]
B = [-a for a in A[2*N:3*N]]
res_R = [0] * (N + 1)
res_B = [0] * (N + 1)
res_R[0] = sum(R)
res_B[N] = -sum(B)
heapq.heapify(R)
heapq.heapify(B)
for i in range(N):
    heapq.heappush(R, M[i])
    a = heapq.heappop(R)
    res_R[i+1] = res_R[i] + M[i] - a
    heapq.heappush(B, -M[N-i-1])
    a = heapq.heappop(B)
    res_B[N-i-1] = res_B[N-i] + M[N-i-1] + a
print(max(r - b for r, b in zip(res_R, res_B)))

Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
ai = lambda: list(map(int,input().split()))

n = int(input())
a = ai()

ans = 0
for k in range(n):
    af = a[:n+k]
    ar = a[n+k:]
    aa = sum(sorted(af)[:n]) + sum(sorted(af, reverse=True)[:n])
    ans = max(ans, aa)

print(ans)

ai = lambda: list(map(int,input().split()))

n = int(input())
a = ai()

big = sum(a[:n])
small = sum(a[2*n:])

import heapq
af = a[:n]
heapq.heapify(af)
ar = [-i for i in a[2*n:]]
heapq.heapify(ar)

ans = [[0,0] for _ in range(n+1)]
ans[0][0] = big
ans[-1][1] = small

for k in range(n):
    if af[0] < a[n+k]:
        b = heapq.heapreplace(af, a[n+k])
        big += a[n+k] - b
    ans[k+1][0] = big

for k in range(n):
    if -ar[0] > a[-n-k-1]:
        s = heapq.heapreplace(ar, -a[-n-k-1])
        small += a[-n-k-1] + s
    ans[-k-2][1] = small

print(max(i-j for i,j in ans))


Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    heapq.heappop(P)
    sp = sum(P)
    p[i] = sum(Q)
for i in range(1,N+1):
    heapq.heappush(Q,-R[-i])
    heapq.heappop(Q)
    sq = sum(Q)
    q[i] = sq

ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)


N = int(input())
A = list(map(int,input().split()))
S = []
for i in range(N+1):
    P = A[:(N+i)]
    Q = A[(N+i):]
    for l in range(len(Q)):
        Q[l] *= -1
    heapq.heapify(P)
    heapq.heapify(Q)
    j = 0
    k = 0
    while j < i:
        heapq.heappop(P)
    while k < N-i:
        heapq.heappop(Q)
    s = sum(P) + sum(Q)
    S.append(s)
ans = min(S)
print(ans)

N = int(input())
A = list(map(int,input().split()))
S = []
import heapq
for i in range(N+1):
    P = A[:(N+i)]
    Q = A[(N+i):]
    for l in range(len(Q)):
        Q[l] *= -1
    heapq.heapify(P)
    heapq.heapify(Q)
    j = 0
    k = 0
    while j < i:
        heapq.heappop(P)
        j += 1
    while k < N-i:
        heapq.heappop(Q)
        k += 1
    s = sum(P) + sum(Q)
    S.append(s)
ans = min(S)
print(ans)

N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    x = heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    y = heapq.heappop(Q)
    sp = sp + R[i-1] - x
    sq = sq - R[-i] - y
    p[i] = sp
    q[i] = sq
ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)


Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import heapq
import sys
def main():
    N = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    front = []
    back = []
    heapq.heapify(front)
    heapq.heapify(back)
    ans = 0
    L = 3*N
    f_end = 0
    b_start = L-1
    for i in range(L):
        a = A[i]
        b = A[3*N-1-i]
        if i == 3*N-1-i:
            s1 = a-front[0]
            s2 = -b-back[0]
            if f_end > b_start:break
            if s1 >= s2 >= 0:
                heapq.heappop(front)
                heapq.heappush(front,a)
                break
            elif 0 <= s1 < s2:
                heapq.heappop(back)
                heapq.heappush(back,-b)
                break
        if len(front) == N:
            if front[0] < a:
                if i < b_start:
                    heapq.heappop(front)
                    heapq.heappush(front,a)
                    f_end = i
        else:
            heapq.heappush(front,a)
            f_end = i
        if len(back) == N:
            if back[0] < -b:
                if f_end < 3*N-1-i:
                    heapq.heappop(back)
                    heapq.heappush(back,-b)
                    b_start = 3*N-1-i
        else:
            heapq.heappush(back,-b)
            b_start = 3*N-1-i
    ans = sum(front)+sum(back)
    print(ans)
    print(front)
    print(back)

if __name__ == "__main__":
    main()

import heapq
import sys
def main():
    N = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    front = A[:N]
    back = list(map(lambda x:x*(-1),A[2*N:]))
    heapq.heapify(front)
    heapq.heapify(back)
    s1 = sum(front)
    s2 = sum(back)
    s1_list = [s1]
    ans = 0
    for i in range(N,2*N):
        a = A[i]
        heapq.heappush(front,a)
        min_front = heapq.heappop(front)
        s1 = s1-min_front+a
        s1_list.append(s1)
    ans = s2 +s1_list.pop()
    for i in reversed(range(N,2*N)):
        b = -A[i]
        heapq.heappush(back,b)
        min_back = heapq.heappop(back)
        s2 = s2-min_back+b
        ans = max(ans,s2+s1_list.pop())
    print(ans)

if __name__ == "__main__":
    main()

Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import heapq
n = int(input())
xs = list(map(int, input().split()))
head = heapq.heapify(xs[:n])
body = xs[n:2*n]
body_and_tail = sorted(xs[n:])
sum_tail = sum(body_and_tail_list[:n])
unused_tail = heapq.heapify(body_and_tail[-n:])
ans = -1000000000000000000000
temp = sum(head) - sum_tail
for b in body:
    heapq.push(head, b)
    temp = temp - heapq.pop(head) - heapq.pop(unused_tail) + 2*b
    ans = max(ans, temp)
print(ans)

import heapq
n = int(input())
xs = list(map(int, input().split()))
head = [(x, x) for x in xs[:n]]
heapq.heapify(head)
body = xs[n:-n]
tail = [(-x, x) for x in xs[-n:]]
heapq.heapify(tail)

def f(heap, body, sign, initial):
    answer = [initial]
    acc = initial
    for b in body:
        heapq.heappush(heap, (sign*b, b))
        _, x = heapq.heappop(heap)
        acc = acc + b - x
        answer.append(acc)
    return answer
 
print(max(x - y for x, y in zip(
    f(head, body, 1, sum(xs[:n])),
    f(tail, body[::-1], -1, sum(xs[-n:]))[::-1])))

Verdicts: Runtime Error

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
from bisect import bisect_left, insort
N = int(input())
A = inpl()

before = sorted(A[:N])
middle = sorted(A[N:-N])
after = sorted(A[-N:])

S_before = [sum(before)]
S_after = [sum(after)]

for m in middle:
    if before[0] < m:
        S_before.append(S_before[-1] + m - before[0])
        insort(before, m)
        before = before[1:]
    else:
        S_before.append(S_before[-1])

for m in middle[::-1]:
    if after[-1] > m:
        S_after.append(S_after[-1] - m + after[-1])
        insort(after, m)
        after = after[:-1]
    else:
        S_after.append(S_after[-1])    

print(max([b-a for b, a in zip(S_before, S_after[::-1])])) 


# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from heapq import heapify, heapreplace 

N = int(input())
A = inpl()
L = A[:N]
M = A[N:2*N]
R = [-a for a in A[2*N:]]
ans = sum(L) + sum(R)
heapify(L)
heapify(R)


i = 0
j = N+1

S = [0]*(N+1)

s = 0
for i, m in enumerate(M):
    if m > L[0]:
        s += m - heapreplace(L, m)
    S[i+1] += s

s = 0
for i, m in enumerate(M[::-1]):
    if m < -R[0]:
        s += -m - heapreplace(R, -m)
    S[-i-2] += s

ans += max(S)
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
import heapq
import bisect

n = int(input())
n = n*3
a = list(map(int,input().split()))

big = a[0:n//3]
tempmin = a[n//3::]
tempmin.sort()
small = tempmin[0:n//3]
spare = tempmin[n//3::]

ans = sum(big)-sum(small)
mxm = ans

heapq.heapify(small)
heapq.heapify(spare)

for i in range(n//3,2*n//3):
    if len(spare) != 0 and a[i] >= spare[0]:
        index = bisect.bisect_left(spare,a[i])
        spare.pop(index)

    if a[i] > big[0]:
        ans += a[i]-big[0]
        index = bisect.bisect_left(big,a[i])
        big.insert(index,a[i])
        big.pop(0)
    
    if a[i] < small[-1]:
        ans -= spare[0]-a[i]
        heapq.heappush(small,spare[0])
        heapq.heappop(spare)
        index = bisect.bisect_left(small,a[i])
        small.pop(index)
    
    if ans > mxm:
        mxm = ans
print(mxm)

import heapq
import bisect

n = int(input())
n = n*3
a = list(map(int,input().split()))

left = a[0:n//3]
right = list(-i for i in a[2*n//3:])

leftsum = [0 for i in range(n//3+1)]
rightsum = [0 for i in range(n//3+1)]

heapq.heapify(left)
leftsum[0] = sum(left)
for i in range(n//3):
    k = i + n//3
    heapq.heappush(left,a[k])
    temp = heapq.heappop(left)
    leftsum[i+1] = leftsum[i]+a[k]-temp

heapq.heapify(right)
rightsum[-1] = -sum(right)
for i in range(n//3)[::-1]:
    k = i + n//3
    heapq.heappush(right,-a[k])
    temp = -heapq.heappop(right)
    rightsum[i] = rightsum[i+1] - temp + a[k]




mxm = -sum(a)
for i in range(n//3+1):
    if leftsum[i]-rightsum[i] > mxm:
        mxm = leftsum[i]-rightsum[i]
print(mxm)

Verdicts: Runtime Error

Accepted
Problem: Let N be a positive integer.  There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').  Find the maximum possible score of a'.

Submission attempts (in order):
# coding: utf-8
# Your code here!
n = int(input())
a = [int(i) for i in input().split()]

from heapq import *

pq1 = a[:n]
heapify(pq1)
s = sum(pq1)
score1 = [s]
for i in range(n):
    c=heappushpop(pq1, a[n+i])
    s += a[n+i] - c
    score1.append(s)

pq2 = [-i for i in a[2*n:]]
heapify(pq2)
s = sum(pq2)
score2 = [s]
for i in range(1,n+1):
    c=heappushpop(pq2, -a[2*n-i])
    s += -a[2*n-i] - c
    score2.append(s)

print(score1)
print(score2)
ans = -10**17
for i,j in zip(score1,reversed(score2)):
    ans = max(ans, i+j)

print(ans)
    


# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

from heapq import *

def get(q,a):
    v = sum(q)
    res = [v]
    for i in a[n:2*n]:
        x = heappushpop(q,i)
        v += i-x
        res.append(v)
    return res

q = a[:n]
heapify(q)
res1 = get(q,a)

a = [-i for i in a[::-1]]
q = a[:n]
heapify(q)
res2 = get(q,a)

#print(res1)
#print(res2)

print(max(i+j for i,j in zip(res1,res2[::-1])))









Verdicts: Wrong Answer

Accepted