結果

問題 No.3670 Fast Knapsack
コンテスト
ユーザー D M
提出日時 2026-09-09 12:23:07
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,801 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,969 ms
コンパイル使用メモリ 344,296 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-09-09 12:23:20
合計ジャッジ時間 11,185 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, limit) for (long long i = (long long)x; i < (long long)limit; i++)
#define REP(i, x, limit) for (long long i = (long long)x; i <= (long long)limit; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el '\n'
#define spa " "
#define inp(x) for(auto &i:x)cin>>i
using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--){
        int n,s;
        cin >> n >> s;

        vector<int> A(n);
        inp(A);

        // Sより大きいものは絶対使わない
        vector<int> B;
        for(auto a:A){
            if(a<=s) B.push_back(a);
        }

        sort(all(B));

        // 全部選べるならそれが最大
        ll sum=0;
        for(auto a:B) sum+=a;

        if(sum<=s){
            cout<<sum<<el;
            continue;
        }

        vector<int> small,large;

        for(auto a:B){
            if(2*a<=s) small.push_back(a);
            else large.push_back(a);
        }

        // dp[x] = smallだけで和xを作れる
        int W=s/64+1;
        vector<ull> dp(W);
        dp[0]=1ULL;

        // dp |= dp << shift
        auto shift_or = [&](int shift){
            int ws=shift/64;
            int bs=shift%64;

            for(int i=W-1;i>=0;i--){
                ull add=0;

                if(i-ws>=0){
                    add |= dp[i-ws]<<bs;
                }

                if(bs && i-ws-1>=0){
                    add |= dp[i-ws-1]>>(64-bs);
                }

                dp[i]|=add;
            }
        };

        // smallを同じ値ごとにまとめる
        for(int i=0;i<(int)small.size();){
            int j=i;

            while(j<(int)small.size() && small[j]==small[i]){
                j++;
            }

            int cnt=j-i;
            int k=1;

            while(cnt>0){
                int take=min(k,cnt);

                ll shift=1LL*small[i]*take;

                if(shift<=s){
                    shift_or(shift);
                }

                cnt-=take;
                k*=2;
            }

            i=j;
        }

        auto can = [&](int x)->bool{
            return (dp[x/64]>>(x%64))&1ULL;
        };

        // largeを使わない場合
        int j=s;

        while(j>=0 && !can(j)){
            j--;
        }

        int ans=j;

        // largeは最大1個しか使えない
        // largeはBから作ったので既に昇順
        for(auto a:large){
            j=min(j,s-a);

            while(j>=0 && !can(j)){
                j--;
            }

            if(j>=0){
                ans=max(ans,a+j);
            }
        }

        cout<<ans<<el;
    }
}
0