#252292 (Python3) No.710 チーム戦

• 問題: No.710 チーム戦
• ユーザー: しらっ亭
• 提出日時: 2018-04-18 03:21:17
• 言語: Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
• 結果: AC
• 実行時間: 1,101 ms / 3,000 ms
• コード長: 640 bytes
• コンパイル時間: 337 ms
• コンパイル使用メモリ: 10,880 KB
• 実行使用メモリ: 10,040 KB
• 最終ジャッジ日時: 2023-09-09 11:17:25
• 合計ジャッジ時間: 10,893 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	16 ms; 7,844 KB
testcase_01	AC	16 ms; 7,752 KB
testcase_02	AC	327 ms; 8,792 KB
testcase_03	AC	351 ms; 8,696 KB
testcase_04	AC	390 ms; 8,836 KB
testcase_05	AC	306 ms; 8,776 KB
testcase_06	AC	390 ms; 8,788 KB
testcase_07	AC	336 ms; 8,784 KB
testcase_08	AC	398 ms; 8,764 KB
testcase_09	AC	344 ms; 8,608 KB
testcase_10	AC	327 ms; 8,648 KB
testcase_11	AC	356 ms; 8,704 KB
testcase_12	AC	401 ms; 8,732 KB
testcase_13	AC	377 ms; 8,688 KB
testcase_14	AC	362 ms; 8,812 KB
testcase_15	AC	359 ms; 8,784 KB
testcase_16	AC	403 ms; 8,664 KB
testcase_17	AC	356 ms; 8,784 KB
testcase_18	AC	373 ms; 8,776 KB
testcase_19	AC	431 ms; 8,964 KB
testcase_20	AC	378 ms; 8,668 KB
testcase_21	AC	394 ms; 8,784 KB
testcase_22	AC	1,101 ms; 10,040 KB
testcase_23	AC	17 ms; 7,756 KB
testcase_24	AC	1,034 ms; 9,816 KB
testcase_25	AC	15 ms; 7,724 KB
testcase_26	AC	16 ms; 7,820 KB

ソースコード

def solve(n, P):
	P.sort(key=sum)
	sum_b = 0

	aa = bb = 0
	for a, b in P:
		if a < b:
			aa += a
		elif a > b:
			bb += b
		else:
			if aa < bb:
				aa += a
			else:
				bb += b
		sum_b += b
	ma = max(aa, bb)

	dp = [0] * ma
	t = 1
	for a, b in P:
		for j in range(min(t, ma - a - 1), -1, -1):
			dp[j + a] = max(dp[j + a], dp[j] + b)
		t = max(t, min(t, ma - a - 1) + a)

	ans = ma
	for i in range(ma):
		ans = min(ans, max(i, sum_b - dp[i]))

	return ans


def main():
	n = int(input())

	P = [None] * n

	for i in range(n):
		P[i] = tuple(map(int, input().split()))

	ans = solve(n, P)

	print(ans)


if __name__ == '__main__':
	main()