Problem:


Score : 800 points

Problem Statement

There are X+Y+Z people, conveniently numbered 1 through X+Y+Z.
Person i has A_i gold coins, B_i silver coins and C_i bronze coins.

Snuke is thinking of getting gold coins from X of those people, silver coins from Y of the people and bronze coins from Z of the people.
It is not possible to get two or more different colors of coins from a single person.
On the other hand, a person will give all of his/her coins of the color specified by Snuke.

Snuke would like to maximize the total number of coins of all colors he gets.
Find the maximum possible number of coins.

Constraints

1 \leq X

1 \leq Y

1 \leq Z

X+Y+Z \leq 10^5

1 \leq A_i \leq 10^9

1 \leq B_i \leq 10^9

1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:

X Y Z
A_1 B_1 C_1
A_2 B_2 C_2
:
A_{X+Y+Z} B_{X+Y+Z} C_{X+Y+Z}

Output

Print the maximum possible total number of coins of all colors he gets.

Sample Input 1

1 2 1
2 4 4
3 2 1
7 6 7
5 2 3

Sample Output 1

18

Get silver coins from Person 1, silver coins from Person 2, bronze coins from Person 3 and gold coins from Person 4.
In this case, the total number of coins will be 4+2+7+5=18.
It is not possible to get 19 or more coins, and the answer is therefore 18.

Sample Input 2

3 3 2
16 17 1
2 7 5
2 16 12
17 7 7
13 2 10
12 18 3
16 15 19
5 6 2

Sample Output 2

110

Sample Input 3

6 2 4
33189 87907 277349742
71616 46764 575306520
8801 53151 327161251
58589 4337 796697686
66854 17565 289910583
50598 35195 478112689
13919 88414 103962455
7953 69657 699253752
44255 98144 468443709
2332 42580 752437097
39752 19060 845062869
60126 74101 382963164

Sample Output 3

3093929975



Sample input:
1 2 1
2 4 4
3 2 1
7 6 7
5 2 3


Sample output:
18

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7


x,y,z=LI()
A=[]
B=[]
C=[]
T=[]
for i in range(x+y+z):
    a,b,c=LI()
    A+=[a]
    B+=[b]
    C+=[c]
    T+=[(a,i,0),(b,i,1),(c,i,2)]

T.sort(reverse=True)
D=[x,y,z]
F=[0]*(x+y+z)
ans=0
for t,j,k in T:
    if D[k] and F[j]==0:
        ans+=t
        D[k]-=1
        F[j]=1

print(ans)

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/agc018/tasks/agc018_c

絶対最大なのは、全員から一番たくさん持ってるコインを貰う事
とりあえずそうして、後から人数を調整することを考える

金と銀を貰いすぎたとする
金をN個減らす、銀をM個減らす、銅をN+M個増やす…？
→必ずしもこうではなさそう…
金を貰いすぎたとする。
貰いすぎたコインを減らし、別のコインを増やす
削った時の減少量が銀にするとA-B , 銅だとA-C
減少量最小化問題になる
→あれなんかやったことがある気が…？

方針違う？
適当にX,Y,Z人で振り分ける
swapすると増える限りswapし続ける？

金銀でswapする場合(1が金→銀)
(B1-A1) + (A2-B2)増える
どちらもheapqに突っ込んで、正な限りswapし続ける？
金銀・金銅・銀銅でやれば最適解になるか？
→そんなことはない(改善できない局所解がある…)

なんもわからん…


=====ちょっと答えを見た=====

まず銅を無視する(金銀だけに分ける)
A-Bで降順ソート(B-A)で昇順ソート
ここで金銀グループはどこかで切って左右にすっぱり分けられる
その中で金銅・銀銅を同様に求めればよい？
→ヒープを使って切り方を全探索

まずX個金・Y+Z個銀グループにしたとする
→銀グループは B-Cで昇順ソート小さいほうからZ個の和*-1 + 大きいほうからY個の和が現在の解

左からX個金・右からZ個銅にして、ずらしていって解を求める
X側では、a-c をヒープに入れ、最小のやつを取り除いて-1をかけて寄与に足せばいい
Z側では逆
"""
import heapq
X,Y,Z = map(int,input().split())
ABC = []
for i in range(X+Y+Z):
    a,b,c = map(int,input().split())
    ABC.append( (b-a , a,b,c) )

ABC.sort()

#金側

q = []
ansX = []
now = 0
for i in range(X):
    tmp,a,b,c = ABC[i]
    heapq.heappush( q , a-c )
    now += a
ansX.append(now)

for i in range(X,X+Z):
    tmp,a,b,c = ABC[i]
    heapq.heappush( q , a-c )
    now += a
    pp = heapq.heappop( q )
    now -= pp
    ansX.append(now)

#銀側
ABC.reverse()

q = []
ansY = []
now = 0
for i in range(Y):
    tmp,a,b,c = ABC[i]
    heapq.heappush( q , b-c )
    now += b
ansY.append(now)

for i in range(Y,Y+Z):
    tmp,a,b,c = ABC[i]
    heapq.heappush( q , b-c )
    now += b
    pp = heapq.heappop( q )
    now -= pp
    ansY.append(now)

ansY.reverse()

#print (ABC)
#print (ansX,ansY)

ans = 0
for i in range(Z):
    ans = max(ans , ansX[i] + ansY[i])
print (ans)

Submission status: Wrong Answer

Solution code:
import heapq
x, y, z = [int(item) for item in input().split()]
gsb = []
for i in range(x + y + z):
    gsb.append([int(item) for item in input().split()])
gsb.sort(key=lambda x: x[0] - x[1], reverse=True)

g_sum = sum(item[0] for item in gsb[:x])
s_sum = sum(item[1] for item in gsb[x+z:x+y+z])
b_sum = sum(item[2] for item in gsb[x:x+z])

gb_pq = [a - c for a, b, c in gsb[:x]]
sb_pq = [b - c for a, b, c in gsb[x+z:x+y+z]]
heapq.heapify(gb_pq)
heapq.heapify(sb_pq)

ans_gb = [0]
gb_total_delta = 0
for a, b, c in gsb[x:x+z]:
    new_gb = a - c
    small_gb = heapq.heappushpop(gb_pq, new_gb)
    gb_total_delta += new_gb - small_gb
    ans_gb.append(gb_total_delta)
ans_sb = [0]
sb_total_delta = 0
for a, b, c in gsb[x:x+z][::-1]:
    new_sb = b - c
    small_sb = heapq.heappushpop(sb_pq, new_sb)
    sb_total_delta = new_sb - small_sb
    ans_sb.append(sb_total_delta)
ans_sb.reverse()

max_delta = 0
for gb, sb in zip(ans_gb, ans_sb):
    max_delta = max(max_delta, gb + sb)
print(g_sum + s_sum + b_sum + max_delta)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
x, y, z = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(x+y+z)]
l.sort(key=lambda x: x[1]-x[0])

res = sum([p[2] for p in l[:z]]) + sum([p[0] for p in l[z:z+x]]) + sum([p[1] for p in l[z+x:]])
is_a = [False for _ in range(x+y+z)]
for i in range(z, z+x):
	is_a[i] = True
rm = z+x-1 #rm: rightmost

a_heap, b_heap = [], []
for i in range(z):
	heappush(a_heap, [l[i][2] - l[i][0], i])

for i in range(z, z+x):
	#print(a_heap[0])
	if l[i][2] - l[i][0] - a_heap[0][0] >= 0:
		#print("hoge")
		is_a[i] = False
		is_a[a_heap[0][1]] = True
		while is_a[rm] == False:
			rm -= 1
		res += l[i][2] - l[i][0] - a_heap[0][0]
		heappop(a_heap)
		heappush(a_heap, [l[i][2] - l[i][0], i])

for i in range(z+x, x+y+z):
	if b_heap == []:
		if l[i][2] - l[i][1] - a_heap[0][0] + l[rm][1] - l[rm][0] >= 0:
			#print("hoge")
			is_a[rm] = False
			is_a[a_heap[0][1]] = True
			res += l[i][2] - l[i][1] - a_heap[0][0] + l[rm][1] - l[rm][0]
			while is_a[rm] == False:
				rm -= 1
			heappop(a_heap)
			heappush(b_heap, l[i][2] - l[i][1])
	elif a_heap == []:
		q = l[i][2] - l[i][1] - b_heap[0]
		if q >= 0:
			res += q
			heappop(b_heap)
			heappush(b_heap, l[i][2] - l[i][1])
	else:
		p = l[i][2] - l[i][1] - a_heap[0][0] + l[rm][1] - l[rm][0]
		q = l[i][2] - l[i][1] - b_heap[0]
		if max(p, q) >= 0:
			if p > q:
				is_a[rm] = False
				is_a[a_heap[0][1]] = True
				while is_a[rm] == False:
					rm -= 1
				res += p
				heappop(a_heap)
				heappush(b_heap, l[i][2] - l[i][1])
			else:
				res += q
				heappop(b_heap)
				heappush(b_heap, l[i][2] - l[i][1])
	#print(res)

print(res)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
x, y, z = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(x+y+z)]
l.sort(key=lambda x: x[1]-x[0])

res = sum([p[2] for p in l[:z]]) + sum([p[0] for p in l[z:z+x]]) + sum([p[1] for p in l[z+x:]])
is_a = [False for _ in range(x+y+z)]
for i in range(z, z+x):
	is_a[i] = True
rm = z+x-1 #rm: rightmost

a_heap, b_heap = [], []
for i in range(z):
	heappush(a_heap, [l[i][2] - l[i][0], i])

for i in range(z, z+x):
	#print(a_heap[0])
	if l[i][2] - l[i][0] - a_heap[0][0] > 0:
		#print("hoge")
		is_a[i] = False
		is_a[a_heap[0][1]] = True
		while is_a[rm] == False:
			rm -= 1
		res += l[i][2] - l[i][0] - a_heap[0][0]
		heappop(a_heap)
		heappush(a_heap, [l[i][2] - l[i][0], i])

for i in range(z+x, x+y+z):
	if b_heap == []:
		if l[i][2] - l[i][1] - a_heap[0][0] + l[rm][1] - l[rm][0] > 0:
			#print("hoge")
			is_a[rm] = False
			is_a[a_heap[0][1]] = True
			res += l[i][2] - l[i][1] - a_heap[0][0] + l[rm][1] - l[rm][0]
			while is_a[rm] == False:
				rm -= 1
			heappop(a_heap)
			heappush(b_heap, l[i][2] - l[i][1])
	elif a_heap == []:
		q = l[i][2] - l[i][1] - b_heap[0]
		if q > 0:
			res += q
			heappop(b_heap)
			heappush(b_heap, l[i][2] - l[i][1])
	else:
		p = l[i][2] - l[i][1] - a_heap[0][0] + l[rm][1] - l[rm][0]
		q = l[i][2] - l[i][1] - b_heap[0]
		if max(p, q) > 0:
			if p > q:
				is_a[rm] = False
				is_a[a_heap[0][1]] = True
				while is_a[rm] == False:
					rm -= 1
				res += p
				heappop(a_heap)
				heappush(b_heap, l[i][2] - l[i][1])
			else:
				res += q
				heappop(b_heap)
				heappush(b_heap, l[i][2] - l[i][1])
	#print(res)

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np


x, y, z = map(int, input().split())
n = x + y + z

a = np.zeros((n, ), dtype=np.int64)
b = np.zeros((n, ), dtype=np.int64)
c = np.zeros((n, ), dtype=np.int64)

for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())

sub_ab = b-a

idx_arg = np.argsort(sub_ab)

top = x + z - 1
bottom = x - 1


def solve(mid):
    sub_ac = c[idx_arg[:mid]] - a[idx_arg[:mid]]
    sub_bc = c[idx_arg[mid:]] - b[idx_arg[mid:]]
    idx_arg_ac = np.argsort(sub_ac)
    idx_arg_bc = np.argsort(sub_bc)
    # print(mid, idx_arg_ac, idx_arg_bc)
    # print(mid, idx_arg[:mid][idx_arg_ac], idx_arg[mid:][idx_arg_bc])
    return a[idx_arg[:mid][idx_arg_ac[:x]]].sum() + \
        c[idx_arg[:mid][idx_arg_ac[x:]]].sum() + \
        b[idx_arg[mid:][idx_arg_bc[:y]]].sum() + \
        c[idx_arg[mid:][idx_arg_bc[y:]]].sum()


# for i in range(x, x+z+1):
#     print(solve(i))

while top-bottom > 1:
    middle = (top+bottom)//2
    if solve(middle) > solve(middle+1):
        top = middle
    else:
        bottom = middle

ans = max(solve(top), solve(x+z))
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import*
f=lambda*z:map(int,raw_input().split())
X,Y,Z=f()
P=[]
Q=[]
L=[0]
R=[0]
r=range(X+Y+Z)
A=sorted(map(f,r),key=lambda a:a[0]-a[1])
for i in r:L[i]-=i>Y and heappop(P);a=A[i];L+=[L[i]+a[1]];heappush(P,a[1]-a[2]);R[i]-=i>X and heappop(Q);a=A[~i];R+=[R[i]+a[0]];heappush(Q,a[0]-a[2])
#print max(L[i]+R[~i]for i in range(Y,Y+Z+1))
print max(L[i]+(Y<=i<=Y+Z)*R[~i]for i in r)

Submission status: Wrong Answer

Solution code:
from heapq import*
f=lambda*z:map(int,raw_input().split())
X,Y,Z=f()
P=[]
Q=[]
L=[0]
R=[0]
r=range(X+Y+Z)
A=sorted(map(f,r),key=lambda a:a[0]-a[1])
for i in r:L[i]-=i>Y and heappop(P);a=A[i];L+=[L[i]+a[1]];heappush(P,a[1]-a[2]);R[i]-=i>X and heappop(Q);a=A[~i];R+=[R[i]+a[0]];heappush(Q,a[0]-a[2])
#print max(L[i]+R[~i]for i in range(Y,Y+Z+1))
print max((Y<=i<=Y+Z)*L[i]+R[~i]for i in r)

Submission status: Wrong Answer

Solution code:
from heapq import*
f=lambda*z:map(int,raw_input().split())
X,Y,Z=f()
P=[]
Q=[]
L=[0]
R=[0]
r=range(X+Y+Z)
A=sorted(map(f,r),key=lambda a:a[0]-a[1])
for i in r:L[i]-=i>Y and heappop(P);a=A[i];L+=[L[i]+a[1]];heappush(P,a[1]-a[2]);R[i]-=i>X and heappop(Q);a=A[~i];R+=[R[i]+a[0]];heappush(Q,a[0]-a[2])
#print max(L[i]+R[~i]for i in range(Y,Y+Z+1))
print max(Z<i-Y<0 or L[i]+R[~i]for i in r)

Submission status: Wrong Answer

Solution code:
from heapq import*
f=lambda*z:map(int,raw_input().split())
X,Y,Z=f()
N=X+Y+Z
P=Q=[]
L=[0]
R=[0]
A=sorted(map(f,[0]*N),key=lambda a:a[0]-a[1])
for i in range(N):L+=[L[i]+A[i][1]];heappush(P,A[i][1]-A[i][2]);R+=[R[i]+A[~i][0]];heappush(Q,A[~i][0]-A[~i][2]);L[-1]-=i>=Y and heappop(P);R[-1]-=i>=X and heappop(Q)
print max(L[i]+R[~i]for i in range(Y,N))

Submission status: Wrong Answer

Solution code:
from heapq import*
f=lambda*z:map(int,raw_input().split())
X,Y,Z=f()
N=X+Y+Z
P=Q=[]
L=[0]
R=[0]
A=sorted(map(f,[0]*N),key=lambda a:a[0]-a[1])
for i in range(N):L+=[L[i]+A[i][1]];heappush(P,A[i][1]-A[i][2]);R+=[R[i]+A[~i][0]];heappush(Q,A[~i][0]-A[~i][2]);L[-1]-=i>=Y and heappop(P);R[-1]-=i>=X and heappop(Q)
print max(L[i]+R[~i]for i in range(Y,Y+Z+1))

Submission status: Wrong Answer

Solution code:
x,y,z = map(int,input().split())
ko = []
gou = 0
for i in range(x+y+z):
  a= list(map(int,input().split()))
  a.append(  a[1] -a[0] )
  a.append( a[2] - a[0])
  a.append(a[3]-a[4])
  gou += a[0]
  ko.append(a)
inf = float("inf")
ko = sorted(ko, key=lambda x:-x[5])
for i in range(y):
  gou += ko[i][3]
  ko[i] = [-inf,-inf,-inf,-inf,-inf,-inf]
ko = sorted(ko, key=lambda x:-x[4])
for i in range(z):
  gou += ko[i][4]
print(gou)

Submission status: Wrong Answer

Solution code:
import math

def sum_coin(a,b):
	#転置して該当列を合算
	temp1 = list(map(list, zip(*a)))
	temp2 = list(map(list, zip(*b)))
	coins =	sum(temp1[2][:Y]) +	sum(temp1[3][Y:]) +	sum(temp2[3][:(-X)]) + sum(temp2[1][(-X):])
	return coins

###入力###
input1 = input("").split(" ")
X = int(input1[0])
Y = int(input1[1])
Z = int(input1[2])
N = X + Y + Z
temp = [ input() for _ in range(N) ]
matrix = [None]*N
for i in range(N):
	a = int(temp[i].split(" ")[0])
	b = int(temp[i].split(" ")[1])
	c = int(temp[i].split(" ")[2])
	matrix[i] = [i, a, b, c, (a-b), (b-c), (c-a)]

###処理###
matrix.sort(key=lambda k: k[4]) #(金-銀)で昇順ソート
print(matrix)
head = sorted(matrix[:Y], key=lambda k: k[5], reverse=True) #(銀-銅)で降順ソート
tail = sorted(matrix[Y:], key=lambda k: k[6], reverse=True) #(銅-金)で降順ソート
print("head:",head)
print("tail:",tail)
result = sum_coin(head, tail)
print("coins",result)

# Y<=k<=(N-X)の中でコイン最大値を求める
for k in range(Y,N-X):
	print("k",k)
	#headにmatrix[Y+1]を追加
	if head[0][5] < matrix[k][5]:
		p = 0
	elif head[-1][5] > matrix[k][5]:
		p = len(head) - 1
	else:
		start = 0
		last = len(head) - 1
		p = last
		while (last-start) > 1:
			j = math.ceil((start+last)/2)
			print("j",j)
			if head[j][5] < matrix[k][5] :
				last = j
			elif head[j][5] > matrix[k][5]:
				start = j
			else:
				p = j
				break
			p = last
	head.insert(p,matrix[k])
	
	#tailからmatrix[Y+1]を削除
	tail.pop(tail.index(matrix[k]))
	print("head:",head)
	print("tail:",tail)
	coins = sum_coin(head, tail)
	print("coins",coins)
	#暫定１位更新
	if result < coins:
		result = coins

###出力###
print(result)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
from heapq import*
X,Y,Z=map(int,raw_input().split());N=X+Y+Z
A=[]
for _ in [0]*N:A.append(map(int,raw_input().split()))
A.sort(cmp=lambda a,b:a[0]-a[1]<b[0]-b[1])
q1=[];q2=[];L=[0];R=[0]
for i in range(N):
	L.append(L[i]+A[i][1]);
	heappush(q1,A[i][1]-A[i][2])
	if i>=Y:L[i+1]-=heappop(q1)
	R.append(R[i]+A[N-1-i][0])
	heappush(q2,A[N-1-i][0]-A[N-1-i][2])
	if i>=X:R[i+1]-=heappop(q2)
print max(L[i]+R[N-i] for i in range(Y,N-X+1))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    X,Y,Z = LI()
    xyz = []
    for _ in range(X+Y+Z):
        x,y,z = LI()
        xyz.append((x,y,z,x-y,y-z,z-x))

    xyz.sort(key=lambda _: _[3] - _[2])
    xs = xyz[Y+Z:]
    yz = xyz[:Y+Z]
    yz.sort(key=lambda _: _[4])
    ys = yz[Z:]
    zs = yz[:Z]

    f = True
    while f:
        f = False
        xs.sort(key=lambda _: _[3])
        ys.sort(key=lambda _: -_[3])
        for i in range(min(X,Y)):
            if xs[i][3] - ys[i][3] >= 0:
                break
            # print('xy', xs[i],ys[i])
            xs[i],ys[i] = ys[i],xs[i]
            f = True

        ys.sort(key=lambda _: _[4])
        zs.sort(key=lambda _: -_[4])
        for i in range(min(Y,Z)):
            if ys[i][4] - zs[i][4] >= 0:
                break
            # print('yz', ys[i],zs[i])
            ys[i],zs[i] = ys[i],zs[i]
            f = True

        zs.sort(key=lambda _: _[5])
        xs.sort(key=lambda _: -_[5])
        for i in range(min(Z,X)):
            if zs[i][5] - xs[i][5] >= 0:
                break
            # print('zx', zs[i],xs[i])
            zs[i],xs[i] = zs[i],xs[i]
            f = True

        xs.sort(key=lambda _: _[3])
        ys.sort(key=lambda _: _[4])
        zs.sort(key=lambda _: _[5])

        for i in range(min([X,Y,Z])):
            if xs[i][3] + ys[i][4] + zs[i][5] >= 0:
                break
            # print('xyz1', xs[i],ys[i],zs[i])
            xs[i],ys[i],zs[i] = zs[i],xs[i],ys[i]
            f = True

        for i in range(min([X,Y,Z])):
            if xs[-i-1][5] + ys[-i-1][3] + zs[-i-1][4] <= 0:
                break
            # print('xyz2', xs[-i-1],ys[-i-1],zs[-i-1])
            xs[-i-1],ys[-i-1],zs[-i-1] = ys[-i-1],zs[-i-1],xs[-i-1]
            f = True

    r = 0
    # print(xs)
    # print(ys)
    # print(zs)
    for c in xs:
        r += c[0]
    for c in ys:
        r += c[1]
    for c in zs:
        r += c[2]

    return r




print(main())

Submission status: Time Limit Exceeded

Solution code:
import math

def sum_coin(a,b):
	#転置して該当列を合算
	temp1 = list(map(list, zip(*a)))
	temp2 = list(map(list, zip(*b)))
	coins =	sum(temp1[2][:Y]) +	sum(temp1[3][Y:]) +	sum(temp2[3][:(-X)]) + sum(temp2[1][(-X):])
	return coins

###入力###
input1 = input("").split(" ")
X = int(input1[0])
Y = int(input1[1])
Z = int(input1[2])
N = X + Y + Z
temp = [ input() for _ in range(N) ]
matrix = [None]*N
for i in range(N):
	a = int(temp[i].split(" ")[0])
	b = int(temp[i].split(" ")[1])
	c = int(temp[i].split(" ")[2])
	matrix[i] = [i, a, b, c, (a-b), (b-c), (c-a)]

###処理###
matrix.sort(key=lambda k: k[4]) #(金-銀)で昇順ソート
#print(matrix)
head = sorted(matrix[:Y], key=lambda k: k[5], reverse=True) #(銀-銅)で降順ソート
tail = sorted(matrix[Y:], key=lambda k: k[6], reverse=True) #(銅-金)で降順ソート
#print("head:",head)
#print("tail:",tail)
result = sum_coin(head, tail)
#print("coins",result)

# Y<=k<=(N-X)の中でコイン最大値を求める
for k in range(Y,N-X):
	#print("k",k)
	#headにmatrix[Y+1]を追加
	if head[0][5] < matrix[k][5]:
		p = 0
	elif head[-1][5] > matrix[k][5]:
		p = len(head) - 1
	else:
		#二分探索
		start = 0
		last = len(head) - 1
		p = last
		while (last-start) > 1:
			j = math.ceil((start+last)/2)
			#print("j",j)
			if head[j][5] < matrix[k][5] :
				last = j
			elif head[j][5] > matrix[k][5]:
				start = j
			else:
				p = j
				break
			p = last
	head.insert(p,matrix[k])
	
	#tailからmatrix[Y+1]を削除
	tail.pop(tail.index(matrix[k]))
	#print("head:",head)
	#print("tail:",tail)
	coins = sum_coin(head, tail)
	#print("coins",coins)
	#暫定１位更新
	if result < coins:
		result = coins

###出力###
print(result)

Submission status: Time Limit Exceeded

Solution code:
input1 = input("").split(" ")
X = int(input1[0])
Y = int(input1[1])
Z = int(input1[2])
N = X + Y + Z
temp = [ input() for _ in range(N) ]
matrix = [None]*N
for i in range(N):
	a = int(temp[i].split(" ")[0])
	b = int(temp[i].split(" ")[1])
	c = int(temp[i].split(" ")[2])
	matrix[i] = [i, a, b, c, (a-b), (b-c), (c-a)]

###########################################
matrix.sort(key=lambda k: k[4])
result = 0
for k in range(Y,N-X):
	temp1 = sorted(matrix[:k], key=lambda k: k[5], reverse=True)
	temp1 = list(map(list, zip(*temp1)))
	temp2 = sorted(matrix[k:], key=lambda k: k[6], reverse=True)
	temp2 = list(map(list, zip(*temp2)))

	coins =	sum(temp1[2][:Y]) +	sum(temp1[3][Y:]) +	sum(temp2[3][:(N-k-X)]) + sum(temp2[1][(N-k-X):])
	if result < coins:
		result = coins

print(result)

Submission status: Time Limit Exceeded

Solution code:
import heapq

if __name__ == '__main__':
    X, Y, Z = list(map(int, input().split()))
    A = []
    B = []
    C = []
    N = X + Y + Z
    for i in range(N):
        tmp_a, tmp_b, tmp_c = list(map(int, input().split()))
        A.append(tmp_a)
        B.append(tmp_b)
        C.append(tmp_c)

    gold_minus_silver = [(a - b, a, b, c) for (a, b, c) in zip(A, B, C)]
    gold_minus_silver.sort()
    # print(gold_minus_silver)

    # 左側
    left_side = []
    for i in range(0, Y):
        heapq.heappush(left_side, (
            gold_minus_silver[i][2] - gold_minus_silver[i][3], gold_minus_silver[i][2], gold_minus_silver[i][3]))

    left_max = [0 for i in range(Z + 1)]
    for i in range(0, Y):
        left_max[0] += left_side[i][1]
    left_bronze = []
    for K in range(1, Z + 1):
        heapq.heappush(left_side, (gold_minus_silver[K + Y - 1][2] - gold_minus_silver[K + Y - 1][3],
                                   gold_minus_silver[K + Y - 1][2],
                                   gold_minus_silver[K + Y - 1][3]))
        left_bronze.append(heapq.heappop(left_side))
        tmp_max = 0
        for i in range(0, Y):
            tmp_max += left_side[i][1]

        for i in range(0, len(left_bronze)):
            tmp_max += left_bronze[i][2]

        left_max[K] = tmp_max
    # print(left_max)
    # 右側
    right_side = []
    for i in range(Y + Z, N):
        heapq.heappush(right_side, (gold_minus_silver[i][1] - gold_minus_silver[i][3], gold_minus_silver[i][1],
                                    gold_minus_silver[i][3]))
    right_max = [0 for i in range(Z + 1)]
    for i in range(0, X):
        right_max[Z] += right_side[i][1]
    right_bronze = []
    for K in range(Z - 1, -1, -1):
        heapq.heappush(right_side, (gold_minus_silver[K + Y][1] - gold_minus_silver[K + Y][3],
                                    gold_minus_silver[K + Y][1],
                                    gold_minus_silver[K + Y][3]))
        right_bronze.append(heapq.heappop(right_side))
        tmp_max = 0
        for i in range(0, X):
            tmp_max += right_side[i][1]

        for i in range(0, len(right_bronze)):
            tmp_max += right_bronze[i][2]

        right_max[K] = tmp_max
    # print(right_max)

    ans = 0
    for i in range(0, Z + 1):
        if ans < left_max[i] + right_max[i]:
            ans = left_max[i] + right_max[i]

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heappushpop


X, Y, Z = map(int, input().split())
N = X + Y + Z

a = []
a_ordered = []
for _ in range(N):
    a_i = list(map(int, input().split()))
    a.append(a_i)
    heappush(a_ordered, (a_i[0] - a_i[1], a_i[0], a_i[1], a_i[2]))

max_value = 0
for k in range(Y, N - X):
    a_left = a_ordered[:k]
    a_left_ordered = []
    for i, v in enumerate(a_left):
        heappush(a_left_ordered, (v[2] - v[3], v[2], v[3]))

    left_value = 0
    for i in range(k - Y):
        left_value += heappop(a_left_ordered)[2]
    for i in range(k - Y, k):
        left_value += heappop(a_left_ordered)[1]


    a_right = a_ordered[k:N]
    a_right_ordered = []
    for i, v in enumerate(a_right):
        heappush(a_right_ordered, (v[1] - v[3], v[1], v[3]))

    right_value = 0
    for i in range(N - k - X):
        right_value += heappop(a_right_ordered)[2]
    for i in range(N - k - X, N - k):
        right_value += heappop(a_right_ordered)[1]

    total_value = left_value + right_value
    #print(total_value)
    if max_value < total_value:
        max_value = total_value

print(max_value)

Submission status: Time Limit Exceeded

Solution code:
X, Y, Z = map(int, input().split())
N = X + Y + Z

a = []
a_ordered = []
for _ in range(N):
    a_i = list(map(int, input().split()))
    a.append(a_i)
    a_ordered.append((a_i[0] - a_i[1], a_i[0], a_i[1], a_i[2]))

a_ordered.sort(key=lambda x: x[0])

max_value = 0
for k in range(Y, N - X):
    a_left = a_ordered[:k]
    a_left_ordered = []
    for i, v in enumerate(a_left):
        a_left_ordered.append((v[2] - v[3], v[2], v[3]))
    a_left_ordered.sort(key=lambda x: x[0])

    left_value = 0
    for i, v in enumerate(a_left_ordered):
        if i < k - Y:
            left_value += v[2]
        else:
            left_value += v[1]


    a_right = a_ordered[k:N]
    a_right_ordered = []
    for i, v in enumerate(a_right):
        a_right_ordered.append((v[1] - v[3], v[1], v[3]))
    a_right_ordered.sort(key=lambda x: x[0])

    right_value = 0
    for i, v in enumerate(a_right_ordered):
        if i < N - k - X:
            right_value += v[2]
        else:
            right_value += v[1]
    total_value = left_value + right_value
    #print(total_value)
    if max_value < total_value:
        max_value = total_value

print(max_value)

Submission status: Time Limit Exceeded

Solution code:
X, Y, Z = list(map(int, input().split(" ")))
 
ABC = []
 
for i in range(X+Y+Z):
    ABC.append(list(map(int, input().split(" "))))

ABC = sorted(ABC, key=lambda row: row[0]-row[1])    
 
ans = 0
 
ABC_bk = ABC[:Y]
ABC_ak = ABC[Y:]
 
for k in range(Y, Y+Z):
    
    if k > Y:
        ABC_bk.append(ABC_ak.pop(0))
    
    before_k = sorted(ABC_bk, key=lambda row: row[1]-row[2])
    after_k = sorted(ABC_ak, key=lambda row: row[0]-row[2])      
    
    if k == Y:
        bk_sum = list(map(sum,zip(*before_k[-Y:])))[1]
    else:
        bk_sum = list(map(sum,zip(*before_k[-Y:])))[1] + list(map(sum,zip(*before_k[:-Y])))[2]
    
    ak_sum = list(map(sum,zip(*after_k[-X:])))[0] + list(map(sum,zip(*after_k[:-X])))[2]
    
    tmp = ak_sum + bk_sum
                          
    if ans < tmp:
        ans = tmp

    
print (ans)

Submission status: Time Limit Exceeded

Solution code:
X, Y, Z = list(map(int, input().split(" ")))

import numpy as np

ABC = []

for i in range(X+Y+Z):
    ABC.append(list(map(int, input().split(" "))))

ABC = sorted(ABC, key=lambda row: row[0]-row[1])    

ans = 0

ABC_bk = ABC[:Y]
ABC_ak = ABC[Y:]

for k in range(Y, Y+Z):
    
    if k > Y:
        ABC_bk.append(ABC_ak.pop(0))
    
    before_k = np.asarray(sorted(ABC_bk, key=lambda row: row[1]-row[2]))
    after_k = np.asarray(sorted(ABC_ak, key=lambda row: row[0]-row[2]))      
    
    bk_sum = before_k[-Y:].sum(axis=0)[1] + before_k[:-Y].sum(axis=0)[2]
    ak_sum = after_k[-X:].sum(axis=0)[0] + after_k[:-X].sum(axis=0)[2]
    
    tmp = ak_sum + bk_sum
                          
    if ans < tmp:
        ans = tmp
        
        
    
    
print (ans)

Submission status: Time Limit Exceeded

Solution code:
X, Y, Z = list(map(int, input().split(" ")))

import numpy as np

ABC = []

for i in range(X+Y+Z):
    ABC.append(list(map(int, input().split(" "))))

ABC = sorted(ABC, key=lambda row: row[0]-row[1])    

ABC_np = np.asarray(ABC)
ans = 0

for k in range(Y, Y+Z):
    before_k = np.asarray(sorted(ABC_np[:k].tolist(), key=lambda row: row[1]-row[2]))
    after_k = np.asarray(sorted(ABC_np[k:].tolist(), key=lambda row: row[0]-row[2]) )      
    
    bk_sum = before_k[-Y:].sum(axis=0)[1] + before_k[:-Y].sum(axis=0)[2]
    ak_sum = after_k[-X:].sum(axis=0)[0] + after_k[:-X].sum(axis=0)[2]
    
    tmp = ak_sum + bk_sum
                          
    if ans < tmp:
        ans = tmp
    

    
print (ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
X, Y, Z = map(int, input().split())
N = X + Y + Z
arys_orig = []
arys = []
for i in range(N):
    tmp = input()
    ary = [int(a) for a in tmp.split()]
    arys_orig.append(ary)
    m = max(ary)
    ary2 = [a - m for a in ary]
    arys.append(ary2)


def argsort(ary):
    x, y, z = ary
    if x < y:
        if y < z:
            return (0, 1, 2)
        elif x < z:
            # x < z <= y
            return (0, 2, 1)
        else:
            # z <= x < y
            return (2, 0, 1)
    else:
        # y <= x
        if x < z:
            # y <= x < z
            return (1, 0, 2)
        elif y < z:
            # y < z <= x
            return (1, 2, 0)
        else:
            # z <= y <= x
            return (2, 1, 0)


remain = [X, Y, Z]
choice = [None for i in range(N)]
for i, ary in enumerate(arys):
    so = argsort(ary)
    for s in so[::-1]:
        if remain[s] > 0:
            remain[s] -= 1
            choice[i] = s
            break

change_cand = [[0, 1], [0, 2], [1, 2]]
i = 0
while i < 3:
    changer_2 = change_cand[i]
    changers = [changer_2, changer_2[::-1]]
    max_dis = [None, None]
    max_can = [None, None]
    for j, changer in enumerate(changers):
        for cand in range(N):
            if choice[cand] != changer[0]:
                continue
            get = arys[cand][changer[1]] - arys[cand][changer[0]]
            if max_dis[j] is None or max_dis[j] < get:
                max_dis[j] = get
                max_can[j] = cand
    if max_dis[0] + max_dis[1] > 0:
        choice[max_can[0]], choice[max_can[1]] = choice[max_can[1]], choice[max_can[0]]
        i = 0
    else:
        i += 1
summ = 0
for i in range(N):
    summ += arys_orig[i][choice[i]]
print(summ)

Submission status: Time Limit Exceeded

Solution code:
x, y, z = map(int, input().split())
n = x + y + z
a, b, c = [], [], []
amb, amc, bma, bmc, cma, cmb = [], [], [], [], [], []
for i in range(n):
    ai, bi, ci = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    amb.append(a[i] - b[i])
    amc.append(a[i] - c[i])
    bma.append(b[i] - a[i])
    bmc.append(b[i] - c[i])
    cma.append(c[i] - a[i])
    cmb.append(c[i] - b[i])
for l in [amb, amc, bma, bmc, cma, cmb]:
    l.sort()
tot = 0
cand = set(range(n))
while x + y + z > 0:
    def rm(i):
        cand.remove(i)
        amb.remove(a[i] - b[i])
        amc.remove(a[i] - c[i])
        bma.remove(b[i] - a[i])
        bmc.remove(b[i] - c[i])
        cma.remove(c[i] - a[i])
        cmb.remove(c[i] - b[i])
    for i in cand:
        if x and a[i] - b[i] >= amb[-x] and a[i] - c[i] >= amc[-x]:
            x -= 1
            tot += a[i]
            rm(i)
            break
        if y and b[i] - a[i] >= bma[-y] and b[i] - c[i] >= bmc[-y]:
            y -= 1
            tot += b[i]
            rm(i)
            break
        if z and c[i] - a[i] >= cma[-z] and c[i] - b[i] >= cmb[-z]:
            z -= 1
            tot += c[i]
            rm(i)
            break
    #if found == 0:
        #print(x, y, z, cand)
        #print(amb, amc, a[3]-b[3], a[3]-c[3], amb[-x], amc[-x])
    #exit(0)
print(tot)

Submission status: Accepted

Solution code:
import heapq,sys

input=sys.stdin.readline

X,Y,Z=map(int,input().split())
N=X+Y+Z
coin=[tuple(map(int,input().split())) for i in range(N)]
coin.sort(key=lambda x:x[0]-x[1])
y=[0]*N
S=0
n=0
que=[]
for i in range(N):
    val=coin[i][1]-coin[i][2]
    if Y>n:
        heapq.heappush(que,val)
        S+=val
        n+=1
        y[i]=S
    else:
        if que[0]<val:
            S+=val-que[0]
            heapq.heappop(que)
            heapq.heappush(que,val)
        y[i]=S

x=[0]*N
S=0
n=0
que=[]
for i in range(N-1,-1,-1):
    val=coin[i][0]-coin[i][2]
    if X>n:
        heapq.heappush(que,val)
        S+=val
        n+=1
        x[i]=S
    else:
        if que[0]<val:
            S+=val-que[0]
            heapq.heappop(que)
            heapq.heappush(que,val)
        x[i]=S

base=sum(coin[i][2] for i in range(N))
ans=-1
for i in range(N):
    if i>=Y-1 and N-(i+1)>=X:
        temp=base+x[i+1]+y[i]
        ans=max(ans,temp)
print(ans)