結果

問題 No.974 最後の日までに
ユーザー tcltktcltk
提出日時 2021-07-03 06:20:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,150 bytes
コンパイル時間 1,959 ms
コンパイル使用メモリ 86,780 KB
実行使用メモリ 151,752 KB
最終ジャッジ日時 2023-09-12 11:57:36
合計ジャッジ時間 38,293 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 547 ms
143,952 KB
testcase_01 AC 876 ms
143,852 KB
testcase_02 AC 836 ms
143,728 KB
testcase_03 AC 859 ms
143,980 KB
testcase_04 AC 850 ms
143,696 KB
testcase_05 AC 843 ms
143,800 KB
testcase_06 AC 888 ms
143,812 KB
testcase_07 AC 859 ms
143,756 KB
testcase_08 AC 829 ms
143,688 KB
testcase_09 AC 837 ms
143,748 KB
testcase_10 AC 839 ms
143,760 KB
testcase_11 AC 840 ms
143,732 KB
testcase_12 AC 820 ms
144,116 KB
testcase_13 AC 838 ms
143,776 KB
testcase_14 AC 848 ms
143,964 KB
testcase_15 AC 833 ms
143,848 KB
testcase_16 WA -
testcase_17 AC 837 ms
143,688 KB
testcase_18 AC 830 ms
143,828 KB
testcase_19 AC 842 ms
143,756 KB
testcase_20 AC 836 ms
143,660 KB
testcase_21 AC 825 ms
143,660 KB
testcase_22 AC 839 ms
143,644 KB
testcase_23 WA -
testcase_24 AC 842 ms
143,848 KB
testcase_25 AC 230 ms
83,188 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 894 ms
143,780 KB
testcase_29 AC 218 ms
80,896 KB
testcase_30 AC 893 ms
143,836 KB
testcase_31 AC 220 ms
80,852 KB
testcase_32 AC 221 ms
80,756 KB
testcase_33 AC 648 ms
128,920 KB
testcase_34 AC 915 ms
143,824 KB
testcase_35 AC 215 ms
80,896 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 AC 216 ms
80,852 KB
testcase_39 AC 218 ms
80,708 KB
testcase_40 AC 717 ms
151,612 KB
testcase_41 AC 743 ms
143,924 KB
testcase_42 WA -
testcase_43 AC 917 ms
143,692 KB
testcase_44 WA -
testcase_45 AC 654 ms
128,936 KB
testcase_46 AC 217 ms
80,824 KB
testcase_47 AC 218 ms
80,640 KB
testcase_48 AC 217 ms
80,836 KB
testcase_49 AC 215 ms
80,756 KB
testcase_50 AC 216 ms
80,880 KB
testcase_51 AC 214 ms
80,664 KB
権限があれば一括ダウンロードができます

ソースコード

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