結果

問題 No.2167 Fibonacci Knapsack
コンテスト
ユーザー chineristAC
提出日時 2022-12-05 23:45:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,393 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 174 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 79,616 KB
最終ジャッジ日時 2024-11-18 00:02:00
合計ジャッジ時間 16,031 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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 new_lie(N,W,item):
    res = 0
    for w,v in item[::-1]:
        if w <= W:
            res += f[v]
            W -= w
    return res

def new_lie_strong(N,W,_item):
    res = new_lie(N,W,_item)
    for i in range(N):
        for j in range(i+1,N):
            item = [_item[k] for k in range(N) if k not in (i,j)]
            res = max(res,new_lie(N-2,W,item))
    return res

def solve_writer(N,W,_item):
    item = [(w,f[v]) for w,v in _item]
    item.sort(key=lambda x:x[1])
    item_sum = [(0,0)]
    for w,v in item:
        last_w,last_v = item_sum[-1]
        item_sum.append((last_w+w,last_v+v))
    
    ans = 0
    w_sum = 0
    v_sum = 0

    for i in range(N)[::-1]:
        w,v = item[i]
        low_w,low_v = item_sum[i]
        if low_w <= W - w_sum:
            ans = max(ans,v_sum+low_v)
        if w <= W - w_sum:
            w_sum += w
            v_sum += v
        
    ans = max(ans,v_sum)
    return ans

def solve_range_first(N,W,item):
    weight = [W+1 for i in range(83)]
    for i in range(N):
        w,v = item[i]
        weight[v] = w
    
    res = 0
    flag = True
    idx = 81
    
    while idx>0:
        if flag and weight[idx] <= W:
            res += f[idx]
            W -= weight[idx]
            idx -= 2
            continue
        
        flag = False
        tmp = [idx-1,idx-2]
        tmp_w = weight[idx-1] + weight[idx-2]
        while tmp[-1] > 0:
            if tmp_w <= W:
                res += f[idx]
                W -= tmp_w
                idx = tmp[-1]
                break
            last = tmp.pop()
            tmp_w = tmp_w - weight[last] + weight[last-1] + weight[last-2]
            tmp.append(last-1)
            tmp.append(last-2)
        idx = idx - 1
        flag = True
    
    return res

def solve_cost_first(N,W,item):
    weight = [W+1 for i in range(83)]
    for i in range(N):
        w,v = item[i]
        weight[v] = w
    
    res = 0
    flag = True
    idx = 81
    while idx:
        cost = W+1
        L = -1
        if flag:
            if weight[idx] < cost:
                cost = weight[idx]
                L = idx-2

        tmp = [idx-1,idx-2]
        tmp_w = weight[idx-1] + weight[idx-2]
        while tmp[-1] > 0:
            if tmp_w < cost:
                cost = tmp_w
                L = tmp[-1]
            last = tmp.pop()
            tmp_w = tmp_w - weight[last] + weight[last-1] + weight[last-2]
            tmp.append(last-1)
            tmp.append(last-2)
        
        if L==-1:
            idx = idx-1
            flag = True
        else:
            res += f[idx]
            W -= cost
            if cost==weight[idx] and flag:
                flag = True
                idx = idx - 2
            else:
                flag = False
                idx = L
    
    return res

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