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:
from sys import stdin
from itertools import repeat
from heapq import heappushpop, heapify
def main():
    x, y, z = map(int, stdin.readline().split())
    n = x + y + z
    dat = map(int, stdin.read().split(), repeat(10, 3 * n))
    ans = 0
    p = []
    for i in xrange(n):
        a, b, c = dat[i*3:i*3+3]
        ans += a
        p.append((b - a, c - a))
    p.sort(reverse=True)
    q = []
    for i in xrange(y):
        ans += p[i][0]
        q.append(p[i][0] - p[i][1])
    heapify(q)
    aa = [ans] * (z + 1)
    for i in xrange(y, y + z):
        t = heappushpop(q, p[i][0] - p[i][1])
        aa[i-y+1] = -t + aa[i-y] + p[i][0]
    q = [-p[i][1] for i in xrange(y + z, n)]
    heapify(q)
    s = [0] * (z + 1)
    for i in xrange(1, z + 1):
        t = heappushpop(q, -p[y+z-i][1])
        s[i] = s[i-1] - t
    print max(aa[i] + s[z-i] for i in xrange(z + 1))
main()

Submission status: Runtime Error

Solution code:
from sys import stdin

a = int(stdin.readline().rstrip())
b = int(stdin.readline().rstrip())
c = int(stdin.readline().rstrip())
x = int(stdin.readline().rstrip())

count = 0

for i in range(a+1):
  if i * 500 > x: continue
  for j in range(b+1):
    if i * 500 + j * 100 > x: continue
    for k in range(c+1):
      if i * 500 + j * 100 + k * 50 == x: count += 1
        
print(count)

Submission status: Runtime Error

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 = [x + y for x, y in zip(*before_k[-Y:])][1]
    else:
        bk_sum = [x + y for x, y in zip(*before_k[-Y:])][1] + [x + y for x, y in zip(*before_k[:-Y])][2]
    
    ak_sum = [x + y for x, y in zip(*after_k[-X:])][0] + [x + y for x, y in zip(*after_k[:-X])][2]
    
    tmp = ak_sum + bk_sum
                          
    if ans < tmp:
        ans = tmp

    
print (ans)

Submission status: Runtime Error

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 = 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]))      
    
    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: Runtime Error

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 = ABC_bk.append(ABC_ak[0])
        ABC_ak = 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: Runtime Error

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):
    
    
    
    
    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
        
        
    ABC_bk = ABC_bk.append(ABC_ak[0])
    ABC_ak = ABC_ak.pop(0)
    
print (ans)

Submission status: Runtime Error

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):
    
    ABC_bk = ABC_bk + ABC_ak[0]
    ABC_ak = ABC_ak.pop(0)
    
    
    before_k = np.asarray(sorted(ABC_bk.tolist(), key=lambda row: row[1]-row[2]))
    after_k = np.asarray(sorted(ABC_ak.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: Runtime Error

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 True:
    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
sum = 0
for i in range(N):
    sum += arys_orig[choice[i]]
print(sum)

Submission status: Runtime Error

Solution code:
# encoding:utf-8
def main():
	N, K = list(map(int, input().split()))
	nums = list(map(int, input().split()))

	max_num = max(nums)
	min_num = min(nums)

	# 最大値が越えてたらだめ
	if K > max_num:
		return("IMPOSSIBLE")

	decomp_min = decomp(min_num)
	for x in decomp_min:
		res = [y % x for y in nums]

		# 共通因子を持ってなかったらだめ
		if max(res) == min(res):
			if K % min_num > 0:
				return("IMPOSSIBLE")
	else:
		return("POSSIBLE")

def decomp(n):
	i = 2
	table = [n]

	while i * i <= n:
		if n % i == 0:
			table.append(int(i))
		i += 1
	return(table)

if __name__ == '__main__':
	print(main())