結果

問題 No.2167 Fibonacci Knapsack
コンテスト
ユーザー chineristAC
提出日時 2022-12-05 23:28:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 215 ms / 2,000 ms
コード長 2,515 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 79,584 KB
最終ジャッジ日時 2024-11-18 00:00:02
合計ジャッジ時間 5,773 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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