結果

問題 No.710 チーム戦
コンテスト
ユーザー hiro5277
提出日時 2026-07-07 23:06:11
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 3,158 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,935 ms
コンパイル使用メモリ 95,692 KB
実行使用メモリ 79,084 KB
最終ジャッジ日時 2026-07-07 23:06:19
合計ジャッジ時間 3,426 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

'''
WAだがいったん提出。同じところの扱いとかダメそう。
DPの仕方を工夫すべき? ABC 204 Dみたいにすべき?

yukicoder No207
方針: ナップザックDP 
dp[i][x] = 問題0,1,2,...,iまで解答して、最後に人xが解答したときに解答時間が最も短くなる時の、[雪男の解答時間, 雪女の解答時間]
*x = 雪男or雪女

入力例1:
3         最後に雪男が解答  最後に雪女が解答
45 50 ->     [45,0]          [0,50]
20 80 ->     [20,50] *1      [45,80]*2
  *1: [65,0]or[20,50]だと[20,50]のほうがよい
  *2: [45,80]or[0,130]だと[0,130]のほうがよい
40 15 ->     [60,50]         [20,65]

メモ:
  i問目まで解けた時点での最短で、i+1問目を解く際の最短を考えれる
  最後に雪男(人0)/雪女(人1)が解いたかで状態を圧縮できる（通常は最大2^100通り）
'''
# 入力
N = int(input())
times = dict({0:[],1:[]}) # times[x][i] = 人xの問題iの解答時間
for i in range(N):
  a,b = list(map(int, input().split()))
  times[0].append(a)
  times[1].append(b)
#print(times)

# DP
dp = [[[0,0],[0,0]] for _ in range(N+1)] # dp[i][x] = i問目を人xが解いて最短時間になるときの[人0の解答時間, 人1の解答時間]
NUM_PERSONS = 2
for i in range(N):
  if(i == 0):
    dp[i][0] = [times[0][i],0]
    dp[i][1] = [0,times[1][i]]
  else:
    # 問題iを人0が解く
    # (1)問題i-1:人0、問題i:人0 が解く
    prev = 0
    tmp_prev1 = dp[i-1][prev]
    tmp_now1 = [tmp_prev1[0]+times[0][i], tmp_prev1[1]]
    solve_time1 = max(tmp_now1)
    sum_times1 = sum(tmp_now1)
    # (2)問題i-1:人1、問題i:人0 が解く
    prev = 1
    tmp_prev2 = dp[i-1][prev]
    tmp_now2 = [tmp_prev2[0]+times[0][i], tmp_prev2[1]]
    solve_time2 = max(tmp_now2)
    sum_time2 = sum(tmp_now2)
    # 比較
    if(solve_time1 < solve_time2):
      dp[i][0] = tmp_now1[:] # コピーしたのを渡した方がよい? -> 変わらず
    elif(solve_time1 == solve_time2): # ここはだいぶ怪しい（先々まで見て考えないとダメな気がする...? 最後に回答している人が同じだから合計が少ないほうでよい?）
      dp[i][0] = tmp_now1[:] if(sum_time1 < sum_time2) else tmp_now2[:]
    else:
      dp[i][0] = tmp_now2[:]
    
    # 問題iを人1が解く
    # (3)問題i-1:人0、問題i:人1 が解く
    prev = 0
    tmp_prev1 = dp[i-1][prev]
    tmp_now1 = [tmp_prev1[0], tmp_prev1[1]+times[1][i]]
    solve_time1 = max(tmp_now1)
    sum_time1 = sum(tmp_now1)
    # (4)問題i-1:人1、問題i:人0 が解く
    prev = 1
    tmp_prev2 = dp[i-1][prev]
    tmp_now2 = [tmp_prev2[0], tmp_prev2[1]+times[1][i]]
    solve_time2 = max(tmp_now2)
    sum_time2 = sum(tmp_now2)
    # 比較
    if(solve_time1 < solve_time2):
      dp[i][1] = tmp_now1[:] 
    elif(solve_time1 == solve_time2):
      dp[i][1] = tmp_now1[:] if(sum_time1 < sum_time2) else tmp_now2[:]
    else:
      dp[i][1] = tmp_now2[:]
#for tmp in dp:
#  print(tmp)

# 最小値を求める
ans = float("inf")
for x in range(NUM_PERSONS):
  solve_time = max(dp[N-1][x])
  ans = min(solve_time, ans)
print(ans)
0