結果

問題 No.974 最後の日までに
ユーザー convexineqconvexineq
提出日時 2021-05-05 02:24:20
言語 PyPy3
(7.3.3)
結果
AC  
実行時間 1,924 ms / 2,000 ms
コード長 761 Byte
コンパイル時間 1,277 ms
使用メモリ 209,848 KB
最終ジャッジ日時 2021-05-05 02:25:33
合計ジャッジ時間 73,306 ms
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 1,780 ms
209,184 KB
testcase_01 AC 1,818 ms
208,012 KB
testcase_02 AC 1,807 ms
206,972 KB
testcase_03 AC 1,804 ms
207,548 KB
testcase_04 AC 1,826 ms
209,180 KB
testcase_05 AC 1,789 ms
206,664 KB
testcase_06 AC 1,826 ms
206,704 KB
testcase_07 AC 1,778 ms
207,688 KB
testcase_08 AC 1,771 ms
207,952 KB
testcase_09 AC 1,811 ms
209,848 KB
testcase_10 AC 1,813 ms
207,508 KB
testcase_11 AC 1,809 ms
207,748 KB
testcase_12 AC 1,848 ms
207,916 KB
testcase_13 AC 1,804 ms
207,540 KB
testcase_14 AC 1,792 ms
207,144 KB
testcase_15 AC 1,844 ms
208,264 KB
testcase_16 AC 1,886 ms
208,516 KB
testcase_17 AC 1,284 ms
206,940 KB
testcase_18 AC 1,340 ms
207,232 KB
testcase_19 AC 1,313 ms
207,056 KB
testcase_20 AC 1,342 ms
207,172 KB
testcase_21 AC 1,330 ms
207,168 KB
testcase_22 AC 1,364 ms
206,896 KB
testcase_23 AC 1,319 ms
207,180 KB
testcase_24 AC 1,359 ms
207,320 KB
testcase_25 AC 49 ms
65,164 KB
testcase_26 AC 65 ms
72,156 KB
testcase_27 AC 1,592 ms
176,144 KB
testcase_28 AC 1,895 ms
207,736 KB
testcase_29 AC 35 ms
54,320 KB
testcase_30 AC 1,506 ms
209,480 KB
testcase_31 AC 35 ms
54,224 KB
testcase_32 AC 35 ms
54,236 KB
testcase_33 AC 1,201 ms
156,512 KB
testcase_34 AC 1,924 ms
208,544 KB
testcase_35 AC 39 ms
54,176 KB
testcase_36 AC 38 ms
54,180 KB
testcase_37 AC 1,665 ms
208,320 KB
testcase_38 AC 35 ms
54,424 KB
testcase_39 AC 36 ms
54,292 KB
testcase_40 AC 1,164 ms
176,548 KB
testcase_41 AC 1,355 ms
209,508 KB
testcase_42 AC 1,701 ms
208,300 KB
testcase_43 AC 1,656 ms
208,464 KB
testcase_44 AC 1,405 ms
177,160 KB
testcase_45 AC 1,131 ms
157,152 KB
testcase_46 AC 36 ms
54,316 KB
testcase_47 AC 36 ms
54,556 KB
testcase_48 AC 36 ms
54,392 KB
testcase_49 AC 35 ms
54,428 KB
testcase_50 AC 35 ms
54,288 KB
testcase_51 AC 36 ms
54,240 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

def dfs(t,m,v,w):
    global ans
    if t==w:
        L.append([m,v])
        return
    dfs(t+1,m+a[t],v,w)
    if t+1 < w: dfs(t+2,m-c[t+1],v+b[t+1],w)

def solve(x,y):
    x.sort(key=f)
    y.sort(key=f)
    for i in range(len(x)-1)[::-1]:
        if x[i][1] < x[i+1][1]: x[i][1] = x[i+1][1]
    ans = idx = 0
    L = len(x)
    for m,v in y[::-1]:
        while idx < L and x[idx][0] + m < 0:
            idx += 1
        if idx < L:
            ans = max(ans,x[idx][1]+v)
    return ans

w = int(input())
a,b,c = [0]*w, [0]*w, [0]*w
for i in range(w):
    a[i],b[i],c[i] = map(int,input().split())
ans = 0
for W in [w//2,w//2+1]:
    f = lambda x:x[0]
    L = x = []
    dfs(0,0,0,W)
    L = y = []
    dfs(W,0,0,w)
    ans = max(ans,solve(x,y))
print(ans)
0