結果
| 問題 |
No.974 最後の日までに
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-31 17:42:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,718 bytes |
| コンパイル時間 | 301 ms |
| コンパイル使用メモリ | 82,428 KB |
| 実行使用メモリ | 137,588 KB |
| 最終ジャッジ日時 | 2025-03-31 17:43:28 |
| 合計ジャッジ時間 | 6,966 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | TLE * 1 -- * 48 |
ソースコード
def main():
import bisect
W = int(input())
weeks = [tuple(map(int, input().split())) for _ in range(W)]
# Initialize DP. dp[i] is a dictionary with keys 0 and 1.
dp = [{} for _ in range(W + 1)]
dp[0][0] = [(0, 0)]
for i in range(1, W + 1):
current_a, current_b, current_c = weeks[i - 1]
current_dp = {}
for s_prev in (0, 1):
if s_prev not in dp[i - 1]:
continue
for m_prev, g_prev in dp[i - 1][s_prev]:
if s_prev == 1:
# Only possible action is date
new_m = m_prev - current_c
new_g = g_prev + current_b
new_s = 0
if new_s not in current_dp:
current_dp[new_s] = []
updated = []
for m, g in current_dp[new_s]:
if not (m <= new_m and g <= new_g):
updated.append((m, g))
dominated = False
for m, g in updated:
if m >= new_m and g >= new_g:
dominated = True
break
if not dominated:
# Remove entries dominated by new entry
temp = []
for m, g in updated:
if not (m <= new_m and g <= new_g):
temp.append((m, g))
temp.append((new_m, new_g))
temp.sort()
current_dp[new_s] = temp
else:
current_dp[new_s] = updated
else:
# s_prev is 0; three possible actions
# Action 1: School
new_s_school = 1 if i < W else 0
new_m_school = m_prev
new_g_school = g_prev
key = new_s_school
if key not in current_dp:
current_dp[key] = []
updated = []
for m, g in current_dp[key]:
if not (m <= new_m_school and g <= new_g_school):
updated.append((m, g))
dominated = False
for m, g in updated:
if m >= new_m_school and g >= new_g_school:
dominated = True
break
if not dominated:
temp = []
for m, g in updated:
if not (m <= new_m_school and g <= new_g_school):
temp.append((m, g))
temp.append((new_m_school, new_g_school))
temp.sort()
current_dp[key] = temp
else:
current_dp[key] = updated
# Action 2: Arubaito
new_m_arubaito = m_prev + current_a
new_g_arubaito = g_prev
new_s_arubaito = 0
key = new_s_arubaito
if key not in current_dp:
current_dp[key] = []
updated = []
for m, g in current_dp[key]:
if not (m <= new_m_arubaito and g <= new_g_arubaito):
updated.append((m, g))
dominated = False
for m, g in updated:
if m >= new_m_arubaito and g >= new_g_arubaito:
dominated = True
break
if not dominated:
temp = []
for m, g in updated:
if not (m <= new_m_arubaito and g <= new_g_arubaito):
temp.append((m, g))
temp.append((new_m_arubaito, new_g_arubaito))
temp.sort()
current_dp[key] = temp
else:
current_dp[key] = updated
# Action 3: Date
new_m_date = m_prev
new_g_date = g_prev
new_s_date = 0
key = new_s_date
if key not in current_dp:
current_dp[key] = []
updated = []
for m, g in current_dp[key]:
if not (m <= new_m_date and g <= new_g_date):
updated.append((m, g))
dominated = False
for m, g in updated:
if m >= new_m_date and g >= new_g_date:
dominated = True
break
if not dominated:
temp = []
for m, g in updated:
if not (m <= new_m_date and g <= new_g_date):
temp.append((m, g))
temp.append((new_m_date, new_g_date))
temp.sort()
current_dp[key] = temp
else:
current_dp[key] = updated
dp[i] = current_dp
max_g = -1
for s_final in (0, 1):
if s_final not in dp[W]:
continue
for m, g in dp[W][s_final]:
if m >= 0 and g > max_g:
max_g = g
print(max_g if max_g != -1 else 0)
if __name__ == "__main__":
main()