結果

問題 No.2167 Fibonacci Knapsack
ユーザー chineristACchineristAC
提出日時 2022-12-05 23:28:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 221 ms / 2,000 ms
コード長 2,515 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 79,900 KB
最終ジャッジ日時 2024-04-29 01:48:07
合計ジャッジ時間 6,119 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 60 ms
63,488 KB
testcase_01 AC 59 ms
63,616 KB
testcase_02 AC 66 ms
65,536 KB
testcase_03 AC 186 ms
79,076 KB
testcase_04 AC 217 ms
79,488 KB
testcase_05 AC 204 ms
79,260 KB
testcase_06 AC 202 ms
79,740 KB
testcase_07 AC 195 ms
79,224 KB
testcase_08 AC 197 ms
79,512 KB
testcase_09 AC 191 ms
79,256 KB
testcase_10 AC 202 ms
79,504 KB
testcase_11 AC 187 ms
79,104 KB
testcase_12 AC 189 ms
79,248 KB
testcase_13 AC 190 ms
79,144 KB
testcase_14 AC 196 ms
78,992 KB
testcase_15 AC 188 ms
79,084 KB
testcase_16 AC 189 ms
78,880 KB
testcase_17 AC 189 ms
79,000 KB
testcase_18 AC 200 ms
79,596 KB
testcase_19 AC 196 ms
79,224 KB
testcase_20 AC 191 ms
79,228 KB
testcase_21 AC 191 ms
78,872 KB
testcase_22 AC 191 ms
79,016 KB
testcase_23 AC 221 ms
79,900 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

f = [0 for i in range(82)]
f[1] = 1
f[2] = 2
for i in range(3,82):
    f[i] = f[i-1] + f[i-2]

def solve(N,W,item,debug=False):
    weight = [W+1 for i in range(83)]
    for i in range(N):
        w,v = item[i]
        weight[v] = w

    def is_packable(pack,debug=False):
        n = len(pack)
        A = [i for i in pack[::-1]]
        dp = [[W+1,W+1] for i in range(n)]

        idx = [A[0]-1,A[0]-2]
        tmp_w = weight[idx[0]] + weight[idx[1]]
        while idx[-1] > 0:
            dp[0][0] = min(dp[0][0],tmp_w)
            dp[0][1] = min(dp[0][1],tmp_w)
            last = idx.pop()
            tmp_w -= weight[last]
            idx.append(last-1)
            idx.append(last-2)
            tmp_w += weight[last-1] + weight[last-2]
        dp[0][1] = min(dp[0][1],weight[A[0]])
    

        for i in range(1,n):
            idx = [A[i]-1,A[i]-2]
            tmp_w = weight[idx[0]] + weight[idx[1]]
            while idx[-1] >= A[i-1]:
                if idx[-1]!=A[i-1]:
                    dp[i][0] = min(dp[i][0],dp[i-1][1]+tmp_w)
                    dp[i][1] = min(dp[i][1],dp[i-1][1]+tmp_w)
                else:
                    dp[i][0] = min(dp[i][0],dp[i-1][0]+tmp_w)
                    dp[i][1] = min(dp[i][1],dp[i-1][0]+tmp_w)
                last = idx.pop()
                tmp_w -= weight[last]
                idx.append(last-1)
                idx.append(last-2)
                tmp_w += weight[last-1] + weight[last-2]
            dp[i][1] = min(dp[i][1],weight[A[i]]+dp[i-1][1])
    
        if debug:
            return min(dp[n-1])
        return min(dp[n-1]) <= W
        
    res = []
    while True:
        if not res:
            M = 81
        else:
            M = res[-1]-2
    
        for i in range(1,M+1)[::-1]:
            if is_packable(res+[i]):
                res.append(i)
                break
        else:
            break
        
    #print(res)
    ans = sum(f[i] for i in res)
    if debug:
        if debug==2:
            print(res)
            return 
        rest_w = W - is_packable(res,debug=True)
        return res,rest_w

    return ans

for _ in range(int(input())):
    N,W = mi()
    w = li()
    item = [(w[i],i+1) for i in range(N)]
    print(solve(N,W,item))
0