結果
| 問題 |
No.974 最後の日までに
|
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 18:35:47 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,097 bytes |
| コンパイル時間 | 180 ms |
| コンパイル使用メモリ | 82,688 KB |
| 実行使用メモリ | 136,216 KB |
| 最終ジャッジ日時 | 2025-06-12 18:36:12 |
| 合計ジャッジ時間 | 6,735 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | TLE * 1 -- * 48 |
ソースコード
def main():
import sys
input = sys.stdin.read
data = input().split()
W = int(data[0])
a_list = []
b_list = []
c_list = []
index = 1
for _ in range(W):
a = int(data[index])
b = int(data[index+1])
c = int(data[index+2])
a_list.append(a)
b_list.append(b)
c_list.append(c)
index += 3
# Precompute required_money using backward DP
required_money = [[0] * 2 for _ in range(W + 2)]
# Initialize week W
for p in [0, 1]:
req_m_list = []
a = a_list[W-1]
c = c_list[W-1]
# School action
req_m = 0 - 0
req_m_list.append(req_m)
# Work action
req_m = 0 - a
req_m_list.append(req_m)
# Date action
if p == 1:
req_m = 0 - (-c)
else:
req_m = 0 - 0
req_m_list.append(req_m)
required_money[W][p] = min(req_m_list)
for i in range(W-1, 0, -1):
for p in [0, 1]:
req_m_list = []
a = a_list[i-1]
c = c_list[i-1]
# School action
new_p_next = 1
req_m_school = required_money[i+1][new_p_next] - 0
req_m_list.append(req_m_school)
# Work action
new_p_next = 0
req_m_work = required_money[i+1][new_p_next] - a
req_m_list.append(req_m_work)
# Date action
if p == 1:
delta = -c
new_p_next = 0
req_m_date = required_money[i+1][new_p_next] - delta
else:
delta = 0
new_p_next = 0
req_m_date = required_money[i+1][new_p_next] - delta
req_m_list.append(req_m_date)
required_money[i][p] = min(req_m_list)
# Forward DP
dp = [[[] for _ in range(2)] for _ in range(W + 2)]
dp[1][0] = [(0, 0)]
max_g = -10**100
for i in range(1, W + 1):
for p_prev in [0, 1]:
current_states = dp[i][p_prev]
for (g_prev, m_prev) in current_states:
if m_prev < required_money[i][p_prev]:
continue
a = a_list[i-1]
b = b_list[i-1]
c = c_list[i-1]
# Action: School
new_p = 1 if i < W else 0
new_g = g_prev - 10**100 if p_prev == 1 else g_prev
new_m = m_prev
if i < W:
if new_m >= required_money[i+1][new_p]:
next_list = dp[i+1][new_p]
dominated = False
for (eg, em) in next_list:
if eg >= new_g and em >= new_m:
dominated = True
break
if not dominated:
new_next_list = []
for (eg, em) in next_list:
if not (eg <= new_g and em <= new_m):
new_next_list.append((eg, em))
new_next_list.append((new_g, new_m))
new_next_list.sort(reverse=True, key=lambda x: x[0])
dp[i+1][new_p] = new_next_list
else:
if new_m >= 0:
max_g = max(max_g, new_g)
# Action: Work
new_p = 0
new_g_work = g_prev - 10**100 if p_prev == 1 else g_prev
new_m_work = m_prev + a
if i < W:
if new_m_work >= required_money[i+1][new_p]:
next_list = dp[i+1][new_p]
dominated = False
for (eg, em) in next_list:
if eg >= new_g_work and em >= new_m_work:
dominated = True
break
if not dominated:
new_next_list = []
for (eg, em) in next_list:
if not (eg <= new_g_work and em <= new_m_work):
new_next_list.append((eg, em))
new_next_list.append((new_g_work, new_m_work))
new_next_list.sort(reverse=True, key=lambda x: x[0])
dp[i+1][new_p] = new_next_list
else:
if new_m_work >= 0:
max_g = max(max_g, new_g_work)
# Action: Date
new_p_date = 0
if p_prev == 1:
new_g_date = g_prev + b
new_m_date = m_prev - c
else:
new_g_date = g_prev
new_m_date = m_prev
if i < W:
if new_m_date >= required_money[i+1][new_p_date]:
next_list = dp[i+1][new_p_date]
dominated = False
for (eg, em) in next_list:
if eg >= new_g_date and em >= new_m_date:
dominated = True
break
if not dominated:
new_next_list = []
for (eg, em) in next_list:
if not (eg <= new_g_date and em <= new_m_date):
new_next_list.append((eg, em))
new_next_list.append((new_g_date, new_m_date))
new_next_list.sort(reverse=True, key=lambda x: x[0])
dp[i+1][new_p_date] = new_next_list
else:
if new_m_date >= 0:
max_g = max(max_g, new_g_date)
print(max_g if max_g != -10**100 else 0)
if __name__ == "__main__":
main()