結果

問題 No.2167 Fibonacci Knapsack
ユーザー chineristACchineristAC
提出日時 2022-12-05 23:28:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 272 ms / 2,000 ms
コード長 2,515 bytes
コンパイル時間 755 ms
コンパイル使用メモリ 86,844 KB
実行使用メモリ 84,312 KB
最終ジャッジ日時 2023-08-11 09:16:46
合計ジャッジ時間 10,272 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 115 ms
78,948 KB
testcase_01 AC 117 ms
78,756 KB
testcase_02 AC 121 ms
78,548 KB
testcase_03 AC 234 ms
83,488 KB
testcase_04 AC 263 ms
84,312 KB
testcase_05 AC 250 ms
83,492 KB
testcase_06 AC 253 ms
83,476 KB
testcase_07 AC 247 ms
83,376 KB
testcase_08 AC 248 ms
83,296 KB
testcase_09 AC 243 ms
82,984 KB
testcase_10 AC 252 ms
83,156 KB
testcase_11 AC 238 ms
82,960 KB
testcase_12 AC 242 ms
83,816 KB
testcase_13 AC 242 ms
83,156 KB
testcase_14 AC 247 ms
82,928 KB
testcase_15 AC 238 ms
82,780 KB
testcase_16 AC 238 ms
83,360 KB
testcase_17 AC 239 ms
83,428 KB
testcase_18 AC 250 ms
83,336 KB
testcase_19 AC 246 ms
83,264 KB
testcase_20 AC 241 ms
83,132 KB
testcase_21 AC 244 ms
83,320 KB
testcase_22 AC 241 ms
82,824 KB
testcase_23 AC 272 ms
83,388 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