結果

問題 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)
0