結果
問題 | No.974 最後の日までに |
ユーザー |
|
提出日時 | 2021-07-03 06:20:41 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,150 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 156,032 KB |
最終ジャッジ日時 | 2024-06-30 00:25:11 |
合計ジャッジ時間 | 29,257 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 WA * 8 |
ソースコード
#!/usr/bin/env python3# from typing import *import sysimport ioimport mathimport collectionsimport decimalimport itertoolsimport bisectimport heapqdef input():return sys.stdin.readline()[:-1]# sys.setrecursionlimit(1000000)# _INPUT = """4# 15 15 20# 15 100 15# 5 15 100# 5 5 35# """# sys.stdin = io.StringIO(_INPUT)W = int(input())A, B, C = [], [], []for _ in range(W):a, b, c = map(int, input().split())A.append(a)B.append(b)C.append(c)A.append(0)B.append(0)C.append(0)N1 = W//2N2 = W-N1dp1 = [list() for _ in range(N1+2)]dp1[0].append((0, 0))for day in range(N1):for money, love in dp1[day]:# 学校 -> デートdp1[day+2].append((money-C[day+1], love+B[day+1]))# アルバイトdp1[day+1].append((money+A[day], love))dp2a = [list() for _ in range(N2+2)]dp2a[0].append((0, 0))for day in range(N2):for money, love in dp2a[day]:# 学校 -> デートdp2a[day+2].append((money-C[N1+day+1], love+B[N1+day+1]))# アルバイトdp2a[day+1].append((money+A[N1+day], love))dp2b = [list() for _ in range(N2+1)]dp2b[0].append((0, 0))for day in range(N2-1):for money, love in dp2b[day]:# 学校 -> デートdp2b[day+2].append((money-C[N1+1+day+1], love+B[N1+1+day+1]))# アルバイトdp2a[day+1].append((money+A[N1+1+day], love))max_love = 0result2a = sorted(dp2a[N2])max_love2a = [0] * (len(result2a)+1)for i in reversed(range(len(result2a))):max_love2a[i] = max(max_love2a[i+1], result2a[i][1])for money1, love1 in dp1[N1]:k = bisect.bisect_left(result2a, (-money1, 0))if k < len(result2a):love2 = max_love2a[k]max_love = max(max_love, love1+love2)result2b = sorted(dp2b[N2-1])max_love2b = [0] * (len(result2b)+1)for i in reversed(range(len(result2b))):max_love2b[i] = max(max_love2b[i+1], result2b[i][1])for money1, love1 in dp1[N1+1]:k = bisect.bisect_left(result2b, (-money1, 0))if k < len(result2b):love2 = max_love2b[k]max_love = max(max_love, love1+love2)print(max_love)