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: Accepted

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側では逆

1WA　→　はい？？？
b-aでソートしたとき同じものをどうするか

1 1 1
1 2 1
99 100 1
1 1 10000
→102

だめなケース見つけたわ
最後のとこだった
"""

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(len(ansX)):
    ans = max(ans , ansX[i] + ansY[i])
print (ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import heapq as hp

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

def compute(A, B, X):
    """左からn番の人まで。AからX人とる。ときの最大スコアを返す。"""
    result = np.zeros(len(A), np.int64)
    result[X - 1] = A[:X].sum()
    q = []
    for i in range(X):
        q.append(A[i] - B[i])
    hp.heapify(q)
    for i in range(X, len(A)):
        x = result[i - 1] + A[i]  # とりあえず A をとる
        loss = hp.heappushpop(q, A[i] - B[i])  # ひとつ B に取り換えたときのロス
        result[i] = x - loss
    return result

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    sig = (i8[:], i8[:], i8)

    cc = CC('my_module')
    cc.export('compute', sig)(compute)
    cc.compile()

from my_module import compute

def main(ABC, X, Y, Z):
    A = ABC[::3]
    B = ABC[1::3]
    C = ABC[2::3]
    ind = np.argsort(C - A)
    A, B, C = A[ind], B[ind], C[ind]
    dp1 = compute(A, B, X)
    dp2 = compute(C[::-1], B[::-1], Z)[::-1]
    x = dp1[X - 1:X + Y] + dp2[X:X + Y + 1]
    return x.max()

X, Y, Z = map(int, readline().split())
ABC = np.array(read().split(), np.int64)

print(main(ABC, X, Y, Z))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import heapq as hp
from numba import njit

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

def compute(A, B, X):
    """左からn番の人まで。AからX人とる。ときの最大スコアを返す。"""
    result = np.zeros(len(A), np.int64)
    result[X - 1] = A[:X].sum()
    q = []
    for i in range(X):
        q.append(A[i] - B[i])
    hp.heapify(q)
    for i in range(X, len(A)):
        x = result[i - 1] + A[i]  # とりあえず A をとる
        loss = hp.heappushpop(q, A[i] - B[i])  # ひとつ B に取り換えたときのロス
        result[i] = x - loss
    return result

def main(ABC, X, Y, Z):
    A = ABC[::3]
    B = ABC[1::3]
    C = ABC[2::3]
    ind = np.argsort(C - A)
    A, B, C = A[ind], B[ind], C[ind]
    q = [0] * 0

    q = [0] * 0
    dp1 = compute(A, B, X)
    dp2 = compute(C[::-1], B[::-1], Z)[::-1]
    x = dp1[X - 1:X + Y] + dp2[X:X + Y + 1]
    return x.max()

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    u1 = numba.from_dtype(np.dtype('U1'))
    sig1 = (i8[:], i8[:], i8)
    sig2 = (i8[:], i8, i8, i8)

    cc = CC('my_module')
    cc.export('compute', sig1)(compute)
    compute = numba.njit(compute)
    cc.export('main', sig2)(main)
    cc.compile()

from my_module import main

X, Y, Z = map(int, readline().split())
ABC = np.array(read().split(), np.int64)

print(main(ABC, X, Y, Z))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import heapq as hp
from numba import njit

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

@njit('i8[:],i8[:],i8', cache=True)
def compute(A, B, X):
    """左からn番の人まで。AからX人とる。ときの最大スコアを返す。"""
    result = np.zeros(len(A), np.int64)
    result[X - 1] = A[:X].sum()
    q = []
    for i in range(X):
        q.append(A[i] - B[i])
    hp.heapify(q)
    for i in range(X, len(A)):
        x = result[i - 1] + A[i]  # とりあえず A をとる
        loss = hp.heappushpop(q, A[i] - B[i])  # ひとつ B に取り換えたときのロス
        result[i] = x - loss
    return result

@njit('(i8[:],i8,i8,i8)', cache=True)
def main(ABC, X, Y, Z):
    A = ABC[::3]
    B = ABC[1::3]
    C = ABC[2::3]
    ind = np.argsort(C - A)
    A, B, C = A[ind], B[ind], C[ind]
    q = [0] * 0

    q = [0] * 0
    dp1 = compute(A, B, X)
    dp2 = compute(C[::-1], B[::-1], Z)[::-1]
    x = dp1[X - 1:X + Y] + dp2[X:X + Y + 1]
    return x.max()

X, Y, Z = map(int, readline().split())
ABC = np.array(read().split(), np.int64)

print(main(ABC, X, Y, Z))

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
from heapq import heappush, heappop

x, y, z = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(x+y+z)]
c.sort(key=lambda x: x[1]-x[0])

ans_l = [-1 for _ in range(x+y+z)]
ans_r = [-1 for _ in range(x+y+z)]

tmp = 0
l = []
for i in range(x):
	tmp += c[i][0]
	heappush(l, (c[i][0] - c[i][2], i))
ans_l[x] = tmp

for i in range(x, x+z):
	tmp += c[i][0]
	heappush(l, (c[i][0] - c[i][2], i))
	p = heappop(l)
	tmp -= c[p[1]][0]
	tmp += c[p[1]][2]
	ans_l[i+1] = tmp

tmp = 0
r = []
for i in range(x+z, x+y+z):
	tmp += c[i][1]
	heappush(r, (c[i][1] - c[i][2], i))
ans_r[x+z] = tmp

for i in range(x+z-1, x-1, -1):
	tmp += c[i][1]
	heappush(r, (c[i][1] - c[i][2], i))
	p = heappop(r)
	tmp -= c[p[1]][1]
	tmp += c[p[1]][2]
	ans_r[i] = tmp

ans = 0
for i in range(x, x+z+1):
	ans = max(ans, ans_l[i] + ans_r[i])

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
x,y,z = map(int,input().split())
n = x+y+z
abc = [list(map(int,input().split())) for i in range(n)]
abc.sort(key = lambda t:t[0]-t[1],reverse=True)
xls = []
ansx = 0
for i in range(x):
  a,b,c = abc[i]
  heappush(xls,(a-c,i))
  ansx += a
yls = []
ansy = 0
for i in range(n-y,n):
  a,b,c = abc[i]
  heappush(yls,(b-c,i))
  ansy += b
ansls = [[0 for i in range(2)] for j in range(z+1)]
ansls[0][0] = ansx
ansls[-1][1] = ansy
for d,ls,w,ans in (0,xls,range(x,x+z),ansx),(1,yls,(range(n-y-1,x-1,-1)),ansy):
  for i in w:
    a,b,c = abc[i]
    if d == 0:
      heappush(ls,(a-c,i))
    else:
      heappush(ls,(b-c,i))
    p,q = heappop(ls)
    ans += -p
    if d == 0:
      ans += a
      ansls[i-x+1][0] = ans
    else:
      ans += b
      ansls[i-n+y+z][1] = ans
print(max([sum(ansls[i]) for i in range(z+1)]))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

X, Y, Z = map(int, input().split())
W = X+Y+Z
ABCs = [tuple(map(int, input().split())) for _ in range(W)]

ABCs.sort(key=lambda x: x[0]-x[1])

sumBCs = [0] * W
sumB = sumC = 0
PQ = []
for i in range(W):
    A, B, C = ABCs[i]
    heappush(PQ, (B-C, i))
    sumB += B
    if len(PQ) > Y:
        _, j = heappop(PQ)
        A, B, C = ABCs[j]
        sumB -= B
        sumC += C
    sumBCs[i] = sumB+sumC

sumACs = [0] * W
sumA = sumC = 0
PQ = []
for i in reversed(range(W)):
    A, B, C = ABCs[i]
    heappush(PQ, (A-C, i))
    sumA += A
    if len(PQ) > X:
        _, j = heappop(PQ)
        A, B, C = ABCs[j]
        sumA -= A
        sumC += C
    sumACs[i] = sumA+sumC

ans = 0
for i in range(Y-1, W-X):
    sumABC = sumBCs[i] + sumACs[i+1]
    ans = max(ans, sumABC)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop
from itertools import accumulate

X, Y, Z, *ABC = map(int, open(0).read().split())

P = sorted(zip(*[iter(ABC)] * 3), key=lambda t: t[0] - t[1])

G = sum(t[0] for t in P[-X:])
S = sum(t[1] for t in P[:Y])
C = sum(t[2] for t in P[Y:-X])

Qg = [a - c for a, b, c in P[-X:]]
heapify(Qg)
B = [0] + [a - c - heappushpop(Qg, a - c) for a, b, c in reversed(P[Y:-X])]

Qs = [b - c for a, b, c in P[:Y]]
heapify(Qs)
F = [0] + [b - c - heappushpop(Qs, b - c) for a, b, c in P[Y:-X]]

print(G + S + C + max(a + b for a, b in zip(accumulate(F), reversed(list(accumulate(B))))))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappop, heappush, heappushpop

X,Y,Z = map(int,readline().split())
m = map(int,read().split())
ABC = sorted(zip(m,m,m), key = lambda x: x[1] - x[0])

# 手前は A or C, 後半はB or Cでとるようにする

# A or Cで、AをX個とるルール
AC = [0] * (X+Y+Z)
q = [] # a -> cと変更する利点をマイナスで格納する
S = 0
for i,(a,b,c) in enumerate(ABC):
    S += a
    d = a - c
    if len(q) < X:
        heappush(q,d)
    else:
        S -= heappushpop(q,d)
    AC[i] = S

# B or Cで、BをY個とるルール
BC = [0] * (X+Y+Z)
q = [] # b -> cと変更する利点をマイナスで格納する
S = 0
for i,(a,b,c) in enumerate(ABC[::-1]):
    S += b
    d = b - c
    if len(q) < Y:
        heappush(q,d)
    else:
        S -= heappushpop(q,d)
    BC[i] = S
BC = BC[::-1]

answer = max(x+y for x,y in zip(AC[X-1:X+Z],BC[X:]))
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from heapq import heappush, heappushpop

"""
銅貨の集合を固定すると、金-銀でソートして貪欲に金をとることになる
逆に金-銀でソートしておくと、金が埋まるまでは金or銅の2択

最後にとる金の番号X+nをfix → 手前は金-銅で貪欲 → queueで管理できる
"""

X,Y,Z = map(int,input().split())
ABC = [[int(x) for x in input().split()] for _ in range(X+Y+Z)]

ABC.sort(key = lambda x: x[0]-x[1],reverse=True)

q = []
sum_a = 0
sum_c = 0
for a,b,c in ABC[:X]:
    # 金を入れる。銅-金の優先度
    heappush(q,(a-c,a))
    sum_a += a
A = [0] * (Z+1)
LC = [0] * (Z+1)
A[0] = sum_a
for i,(a,b,c) in enumerate(ABC[X:X+Z],1):
    sum_a += a
    x,del_a = heappushpop(q,(a-c,a))
    sum_a -= del_a
    sum_c += del_a-x
    A[i] = sum_a
    LC[i] = sum_c

ABC_rev = ABC[::-1]
q = []
sum_b = 0
sum_c = 0
for a,b,c in ABC_rev[:Y]:
    heappush(q,(b-c,b))
    sum_b += b
B = [0] * (Z+1)
RC = [0] * (Z+1)
B[0] += sum_b
for i,(a,b,c) in enumerate(ABC_rev[Y:Y+Z],1):
    sum_b += b
    x,del_b = heappushpop(q,(b-c,b))
    sum_b -= del_b
    sum_c += del_b-x
    B[i] = sum_b
    RC[i] = sum_c

answer = max(sum(x) for x in zip(A,LC,B[::-1],RC[::-1]))
print(answer)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
X, Y, Z = map(int, input().split())
N = X + Y + Z
A, B, C = [], [], []
for i in range(N):
    a, b, c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)

gs = [(A[i] - B[i], i) for i in range(N)]
gs = sorted(gs)

silver = [0] * (Z + 1)

sb = []
for i in range(Y):
    j = gs[i][1]
    heappush(sb, (B[j] - C[j], j))
    silver[0] += B[j]

for i in range(Z):
    j = gs[i + Y][1]
    heappush(sb, (B[j] - C[j], j))
    silver[i + 1] += silver[i] + B[j]
    k = heappop(sb)
    silver[i + 1] -= k[0]

gs = sorted(gs, reverse=True)
gold = [0] * (Z + 1)
gb = []
for i in range(X):
    j = gs[i][1]
    heappush(gb, (A[j] - C[j], j))
    gold[0] += A[j]

for i in range(Z):
    j = gs[i + X][1]
    heappush(gb, (A[j] - C[j], j))
    gold[i + 1] += gold[i] + A[j]
    k = heappop(gb)
    gold[i + 1] -= k[0]

ans = 0
for i in range(Z + 1):
    ans = max(ans, silver[i] + gold[Z - i])

print(ans)

Submission status: Accepted

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: Accepted

Solution code:
import heapq


def main():
    X, Y, Z = map(int, input().split())
    N = X+Y+Z
    P = [None] * N
    for i in range(N):
        A, B, C = map(int, input().split())
        P[i] = (A, B, C)
    P.sort(key=lambda x: x[0] - x[1])
    lsum = [0] * (Z+1)
    lsum[0] = sum(map(lambda x: x[1], P[:Y]))
    h = list(map(lambda x: x[1] - x[2], P[:Y]))
    heapq.heapify(h)
    for i in range(Z):
        heapq.heappush(h, P[Y+i][1] - P[Y+i][2])
        lsum[i+1] = lsum[i] - heapq.heappop(h) + P[Y+i][1]
    # print(lsum)
    rsum = [0] * (Z+1)
    rsum[0] = sum(map(lambda x: x[0], P[N-X:]))
    h = list(map(lambda x: x[0] - x[2], P[N-X:]))
    heapq.heapify(h)
    for i in range(Z):
        heapq.heappush(h, P[N-X-1-i][0] - P[N-X-1-i][2])
        rsum[i+1] = rsum[i] - heapq.heappop(h) + P[N-X-1-i][0]
    # print(rsum)
    ans = 0
    for i in range(Z+1):
        ans = max(lsum[i] + rsum[Z-i], ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from heapq import heappush,heappushpop
x,y,z=map(int,input().split())
ABC=[tuple(map(int,input().split())) for _ in range(x+y+z)]
ABC.sort(key=lambda x: x[0]-x[1])
cy=0
hq=[]
for a,b,c in ABC[:y]:
    cy+=b
    heappush(hq,b-c)
Ly=[cy]
for a,b,c in ABC[y:y+z]:
    cy+=b-heappushpop(hq,b-c)
    Ly.append(cy)
cx=0
hq=[]
for a,b,c in ABC[y+z:]:
    cx+=a
    heappush(hq,a-c)
Lx=[cx]
for a,b,c in reversed(ABC[y:y+z]):
    cx+=a-heappushpop(hq,a-c)
    Lx.append(cx)
print(max(i+j for i,j in zip(Lx[::-1],Ly)))

Submission status: Accepted

Solution code:
X, Y, Z = map(int, input().split())
ans = 0
BC = []
for _ in range(X+Y+Z):
    a, b, c = map(int, input().split())
    ans += a
    BC.append([b-a, c-a])
BC.sort(key=lambda x: x[1]-x[0])
import heapq
q = []
an = 0
for b, _ in BC[:Y]:
    heapq.heappush(q, b)
    an += b
A = [an]
for b, _ in BC[Y:-Z]:
    heapq.heappush(q, b)
    an += b
    b_ = heapq.heappop(q)
    an -= b_
    A.append(an)
q = []
an = 0
for _, c in BC[-Z:]:
    heapq.heappush(q, c)
    an += c
A[-1] += an
for i, (_, c) in enumerate(BC[-Z-1:Y-1:-1], 2):
    heapq.heappush(q, c)
    an += c
    c_ = heapq.heappop(q)
    an -= c_
    A[-i] += an
print(ans + max(A))

Submission status: Accepted

Solution code:
from heapq import heappushpop
import sys
X, Y, Z = map(int, sys.stdin.readline().split())
N = X+Y+Z
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
ABC.sort(key = lambda x: x[0] - x[1], reverse = True)

GB = [None]*N
Q = [a - c for a, _, c in ABC[:X]]
Q.sort()
gs = sum(a for a, _, _ in ABC[:X])
GB[X-1] = gs
for i, (a, b, c) in enumerate(ABC[X:X+Z], X):
    gs += - heappushpop(Q, a - c) + a
    GB[i] = gs

SB = [None]*N
Q = [b - c for _, b, c in ABC[X+Z:]]
Q.sort()
ss = sum(b for _, b, _ in ABC[X+Z:])
SB[-Y-1] = ss
for i, (a, b, c) in enumerate(ABC[X+Z-1:X-1:-1], 1):
    i = -Y - i
    ss += - heappushpop(Q, b - c) + b
    SB[i-1] = ss
print(max(i + j for i, j in zip(GB[X-1:X+Z], SB[X-1:X+Z])))

Submission status: Accepted

Solution code:
import numpy as np
from heapq import heappush, heappop


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)

pq_left = []
pq_right = []

mem = 0

cls = np.zeros((n, ), dtype=np.int64)


for i in range(x):
    mem += a[idx_arg[i]]
    heappush(pq_left, (a[idx_arg[i]]-c[idx_arg[i]], idx_arg[i]))
    cls[idx_arg[i]] = 1

for i in range(x, n):
    mem += c[idx_arg[i]]
    cls[idx_arg[i]] = 3
    heappush(pq_right, (c[idx_arg[i]]-b[idx_arg[i]], idx_arg[i]))
    if(len(pq_right) > z):
        _, idx = heappop(pq_right)
        mem -= c[idx]
        mem += b[idx]
        cls[idx] = 2

ans = mem


for i in range(x, x+z):
    if cls[idx_arg[i]] == 2:
        mem -= b[idx_arg[i]]
        while True:
            _, idx = heappop(pq_right)
            if cls[idx] == 3:
                mem -= c[idx]
                mem += b[idx]
                cls[idx] = 2
                break
    elif cls[idx_arg[i]] == 3:
        mem -= c[idx_arg[i]]
    cls[idx_arg[i]] = 1
    mem += a[idx_arg[i]]
    heappush(pq_left, (a[idx_arg[i]]-c[idx_arg[i]], idx_arg[i]))
    _, idx = heappop(pq_left)
    mem -= a[idx]
    mem += c[idx]
    cls[idx] = 0
    ans = max(ans, mem)

print(ans)

Submission status: Accepted

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))

Submission status: Accepted

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+=[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: Accepted

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,L*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: Accepted

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: Accepted

Solution code:
import heapq
X,Y,Z = map(int,input().split())
N = X+Y+Z
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:x[0]-x[1])

l_opt = [0]*(N+1)
r_opt = [0]*(N+1)

silver = bronze = 0
q_sb = []
heapq.heapify(q_sb)
for i,(g,s,b) in enumerate(src):
    heapq.heappush(q_sb, (s-b, s, b))
    silver += s
    if i >= Y:
        _, s2, b2 = heapq.heappop(q_sb)
        silver -= s2
        bronze += b2
    l_opt[i+1] = silver + bronze

gold = bronze = 0
q_gb = []
heapq.heapify(q_gb)
for i,(g,s,b) in enumerate(reversed(src)):
    heapq.heappush(q_gb, (g-b, g, b))
    gold += g
    if i >= X:
        _, g2, b2 = heapq.heappop(q_gb)
        gold -= g2
        bronze += b2
    r_opt[N-1-i] = gold + bronze

ans = 0
for l,r in list(zip(l_opt, r_opt))[Y:Y+Z+1]:
    ans = max(ans, l+r)
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappushpop
X, Y, Z = map(int, input().split())
xyz = sorted([list(map(int,l.split()))for l in sys.stdin],key=lambda x:x[0]-x[1])

uq = []
cy = 0
for x, y, z in xyz[:Y]:
    heappush(uq, y - z)
    cy += y
Ly = [cy]
for x, y, z in xyz[Y:Y+Z]:
    cy += y - heappushpop(uq, y - z)
    Ly += [cy]

lq = []
cx = 0
for _ in [0] * X:
    x, y, z = xyz.pop()
    heappush(lq, x - z)
    cx += x
Lx = [cx]
for _ in [0] * Z:
    x, y, z = xyz.pop()
    cx += x - heappushpop(lq, x - z)
    Lx += [cx]

print(max(map(sum, zip(Lx, Ly[::-1]))))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappushpop
X, Y, Z = map(int, input().split())
xyz = sorted([list(map(int,l.split()))for l in sys.stdin],key=lambda x:x[0]-x[1])

uq = []
cy = 0
for x, y, z in xyz[:Y]:
    heappush(uq, y - z)
    cy += y
Ly = [cy]
for x, y, z in xyz[Y:Y+Z]:
    cy += y - heappushpop(uq, y - z)
    Ly += [cy]

lq = []
cx = 0
for x, y, z in xyz[-X:]:
    heappush(lq, x - z)
    cx += x
Lx = [cx]
for x, y, z in xyz[Y+Z-1:Y-1:-1]:
    cx += x - heappushpop(lq, x - z)
    Lx += [cx]

print(max(map(sum, zip(Lx, Ly[::-1]))))

Submission status: Accepted

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 = sorted([LI() for _ in range(X+Y+Z)], key=lambda x: x[0]-x[1])
    ys = xyz[:Y]
    yq = []
    tr = 0
    for x,y,z in ys:
        heapq.heappush(yq, y-z)
        tr += y
    ya = [tr]
    for i in range(Z):
        x,y,z = xyz[Y+i]
        tr += y
        heapq.heappush(yq, y-z)
        t = heapq.heappop(yq)
        tr -= t
        ya.append(tr)

    xs = xyz[Y+Z:]
    xq = []
    tr = 0
    for x,y,z in xs:
        heapq.heappush(xq, x-z)
        tr += x
    xa = [tr]
    for i in range(Z):
        x,y,z = xyz[-X-i-1]
        tr += x
        heapq.heappush(xq, x-z)
        t = heapq.heappop(xq)
        tr -= t
        xa.append(tr)

    r = 0
    for a,b in zip(ya, xa[::-1]):
        tr = a+b
        if r < tr:
            r = tr

    return r




print(main())

Submission status: Accepted

Solution code:
from heapq import heapify, heappushpop
from itertools import accumulate

x, y, z = map(int, input().split())
persons = [list(map(int, input().split())) for _ in range(x + y + z)]
persons.sort(key=lambda abc: abc[0] - abc[1])

ans_g = sum(x[0] for x in persons[-x:])
ans_s = sum(x[1] for x in persons[:y])
ans_c = sum(x[2] for x in persons[y:-x])

gold_pq = [a - c for a, b, c in persons[-x:]]
silver_pq = [b - c for a, b, c in persons[:y]]
heapify(gold_pq)
heapify(silver_pq)

ans_f = [0]
for a, b, c in persons[y:-x]:
    np = b - c
    rp = heappushpop(silver_pq, np)
    ans_f.append(np - rp)

ans_b = [0]
for a, b, c in persons[-x - 1:y - 1:-1]:
    np = a - c
    rp = heappushpop(gold_pq, np)
    ans_b.append(np - rp)

ans_f = list(accumulate(ans_f))
ans_b = list(accumulate(ans_b))
print(ans_g + ans_s + ans_c + max(sum(z) for z in zip(ans_f, reversed(ans_b))))

Submission status: Accepted

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_max[K] = left_max[K - 1] + gold_minus_silver[K + Y - 1][2]
        bronze = heapq.heappop(left_side)
        left_max[K] += (bronze[2] - bronze[1])


        # 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_max[K] = right_max[K + 1] + gold_minus_silver[K + Y][1]
        bronze = heapq.heappop(right_side)
        right_max[K] += (bronze[2] - bronze[1])

    # 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: Accepted

Solution code:
from heapq import*
X,Y,Z=map(int,input().split());N=X+Y+Z;A=[];p=[];q=[];L=[0];R=[0]
for _ in[0]*N:A.append([int(e)for e in input().split()])
A.sort(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[-1-i][0]];heappush(q,A[~i][0]-A[~i][2])
	if i>=Y:L[i+1]-=heappop(p)
	if i>=X:R[i+1]-=heappop(q)
print(max(L[i]+R[~i]for i in range(Y,N-X+1)))

Submission status: Accepted

Solution code:
from heapq import*;X,Y,Z=map(int,input().split());N=X+Y+Z;A=[];q1=[];q2=[];L=[0];R=[0]
for _ in[0]*N:A.append([int(e)for e in input().split()])
A.sort(key=lambda a:a[0]-a[1])
for i in range(N):
	L+=[L[i]+A[i][1]];heappush(q1,A[i][1]-A[i][2]);R+=[R[i]+A[-1-i][0]];heappush(q2,A[~i][0]-A[~i][2])
	if i>=Y:L[i+1]-=heappop(q1)
	if i>=X:R[i+1]-=heappop(q2)
print(max(L[i]+R[~i]for i in range(Y,N-X+1)))

Submission status: Accepted

Solution code:
from heapq import*
X,Y,Z=map(int,input().split());N=X+Y+Z;A=[];q1=[];q2=[];L=[0];R=[0]
for _ in[0]*N:A.append([int(e)for e in input().split()])
A.sort(key=lambda a:a[0]-a[1])
for i in range(N):
	L+=[L[i]+A[i][1]];heappush(q1,A[i][1]-A[i][2]);R+=[R[i]+A[-1-i][0]];heappush(q2,A[~i][0]-A[~i][2])
	if i>=Y:L[i+1]-=heappop(q1)
	if i>=X:R[i+1]-=heappop(q2)
print(max(L[i]+R[~i]for i in range(Y,N-X+1)))

Submission status: Accepted

Solution code:
from heapq import*
X,Y,Z=map(int,input().split());N=X+Y+Z;A=[];q1=[];q2=[];L=[0];R=[0]
for _ in[0]*N:A.append([int(e)for e in input().split()])
A.sort(key=lambda a:a[0]-a[1])
for i in range(N):
	L+=[L[i]+A[i][1]];heappush(q1,A[i][1]-A[i][2]);R+=[R[i]+A[-1-i][0]];heappush(q2,A[-1-i][0]-A[-1-i][2])
	if i>=Y:L[i+1]-=heappop(q1)
	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: Accepted

Solution code:
from heapq import*
X,Y,Z=map(int,input().split());N=X+Y+Z;A=[];q1=[];q2=[];L=[0];R=[0]
for _ in[0]*N:A.append([int(e)for e in input().split()])
A.sort(key=lambda a:a[0]-a[1])
for i in range(N):
	L+=[L[i]+A[i][1]];heappush(q1,A[i][1]-A[i][2]);R+=[R[i]+A[N-1-i][0]];heappush(q2,A[N-1-i][0]-A[N-1-i][2])
	if i>=Y:L[i+1]-=heappop(q1)
	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: Accepted

Solution code:
from heapq import*
X,Y,Z=map(int,input().split());N=X+Y+Z;A=[];q1=[];q2=[];L=[0];R=[0]
for _ in[0]*N:A.append([int(e)for e in input().split()])
A.sort(key=lambda a:a[0]-a[1])
for i in range(N):
	L.append(L[i]+A[i][1]);heappush(q1,A[i][1]-A[i][2]);R.append(R[i]+A[N-1-i][0]);heappush(q2,A[N-1-i][0]-A[N-1-i][2])
	if i>=Y:L[i+1]-=heappop(q1)
	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: Accepted

Solution code:
# C(800)
# maximize
import numpy as np
import heapq

X, Y, Z = map(int, input().split())
A_np = np.zeros(X+Y+Z, dtype='int')
B_np = np.zeros(X+Y+Z, dtype='int')
C_np = np.zeros(X+Y+Z, dtype='int')

for i in range(X+Y+Z):
    a, b, c = map(int, input().split())
    A_np[i] = a
    B_np[i] = b
    C_np[i] = c
    
# Bronze -> Gold
order_A_C = np.argsort(A_np - C_np)
A_np_s = A_np[order_A_C]
B_np_s = B_np[order_A_C]
C_np_s = C_np[order_A_C]

# base : Bronze -> Silver -> Gold
res_base = C_np_s[:Z].sum() + B_np_s[Z:(Z+Y)].sum() + A_np_s[(Z+Y):].sum()

# left_diff_heap
C_B_heapq = list(C_np_s[:Z] - B_np_s[:Z])
heapq.heapify(C_B_heapq)

plus_left = np.zeros(Y+1, dtype='int')
for k in range(Y):
    r = heapq.heappushpop(C_B_heapq, C_np_s[Z+k] - B_np_s[Z+k])
    plus_left[k+1] = plus_left[k] - r + C_np_s[Z+k] - B_np_s[Z+k]

# right_diff_heap
A_B_heapq = list(A_np_s[(Z+Y):] - B_np_s[(Z+Y):])
heapq.heapify(A_B_heapq)

plus_right = np.zeros(Y+1, dtype='int')
for k in range(Y):
    r = heapq.heappushpop(A_B_heapq, A_np_s[Z+Y-1-k] - B_np_s[Z+Y-1-k])
    plus_right[Y-k-1] = plus_right[Y-k] - r + A_np_s[Z+Y-1-k] - B_np_s[Z+Y-1-k]
    
print((plus_left+plus_right).max() + res_base)