結果

問題 No.974 最後の日までに
ユーザー tcltk
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#!/usr/bin/env python3
# from typing import *
import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq
def 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//2
N2 = W-N1
dp1 = [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 = 0
result2a = 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0