結果

問題 No.3322 引っ張りだこ
コンテスト
ユーザー 高橋ゆに
提出日時 2025-06-14 23:42:07
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 941 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 67,716 KB
最終ジャッジ日時 2025-10-31 20:30:29
合計ジャッジ時間 5,347 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 1 << 60
ODD = K % 2
EVEN = ODD ^ 1
K2 = K // 2 if EVEN else (K - 1) // 2

def max_score(a: tuple[int,int], b: tuple[int,int]): 
    if a[0] != b[0]:
        return max(a, b)
    else:
        return min(a, b)
    
def alien_dp(cost: int):
    dpa = (0, 0)
    dpb = (-INF, 0)
    for i in range(N):
        ndpa = max_score((dpa[0] + A[i], dpa[1]),(dpb[0] + A[i] - cost * ODD, dpb[1] + ODD))
        ndpb = max_score((dpa[0] + B[i] - cost * EVEN, dpa[1] + EVEN), (dpb[0] + B[i], dpb[1]))
        dpa = ndpa
        dpb = ndpb
    return max(dpa, dpb)
    
score, cnt = alien_dp(0)
if cnt <= K2:
    print(score)
    exit()
    
ng, ok = 0, INF
while ok - ng > 1:
    med = (ng + ok) // 2
    score, cnt = alien_dp(med)
    if cnt > K2:
        ng = med
    else:
        ok = med
score, cnt = alien_dp(ok)
print(score + ok * K2)
0