#1182639 (C++23) No.3670 Fast Knapsack

• 問題: No.3670 Fast Knapsack
• ユーザー: あいすあうと
• 提出日時: 2026-09-04 23:26:07
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 223 ms / 2,500 ms
• コード長: 3,237 bytes
• コンパイル時間: 4,272 ms
• コンパイル使用メモリ: 376,268 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-04 23:26:20
• 合計ジャッジ時間: 9,005 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 25

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using i128=__int128;
using P=pair<ll,ll>;
template<typename T> using vc=vector<T>;
template<typename T> using vv=vc<vc<T>>;
using vl=vc<ll>;
using vvl=vc<vc<ll>>;
using vul=vc<ull>;
using vs=vc<string>;
using vb=vc<bool>;
#define rep(i,s,n) for(ll i=s;i<(n);i++)
#define Rep(i,s,n) for(ll i=n;i>=s;i--)
#define nall(x) x.begin(),x.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define nexp(v) next_permutation(v)
#define prep(v) prev_permutation(v)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define M1 cout<<"-1"<<endl
const long long INF=(1LL<<62)-(1LL<<31)-1;
#define endl '\n'
using mint=modint998244353;
using mint7=modint1000000007;
//vl dx={1,-1,0,0};vl dy={0,0,1,-1};
//vl dx={0,0,1,1,1,-1,-1,-1};vl dy={1,-1,0,1,-1,0,1,-1};
bool out_grid(ll i, ll j, ll h, ll w){return (!(0<=i && i<h && 0<=j && j<w));}
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll ceil_div(ll a,ll b){return (a+(b-1))/b;}

struct DynamicBitsetSubsetSum{
	int S,hi,W;
	vc<ull> bit;

	explicit DynamicBitsetSubsetSum(int max_sum):S(max_sum),hi(0),W((max_sum+64)>>6),bit(W,0){
		bit[0]=1;
	}

private:
	void trim(){
		int rem=(S+1)&63;
		if(rem)bit.back()&=(1ULL<<rem)-1;
	}

public:
	void add(int x){
		assert(x>=0);
		if(x==0||x>S)return;

		int new_hi=(x>S-hi?S:hi+x);
		int word_shift=x>>6;
		int bit_shift=x&63;
		int top=new_hi>>6;

		if(bit_shift==0){
			for(int i=top;i>=word_shift;i--)bit[i]|=bit[i-word_shift];
		}else{
			for(int i=top;i>=word_shift;i--){
				int src=i-word_shift;
				ull v=bit[src]<<bit_shift;
				if(src-1>=0)v|=bit[src-1]>>(64-bit_shift);
				bit[i]|=v;
			}
		}

		hi=new_hi;
		trim();
	}

	bool test(int x)const{
		if(x<0||x>S)return false;
		return(bit[x>>6]>>(x&63))&1ULL;
	}

	int prev(int x)const{
		if(x<0)return -1;
		x=min(x,S);

		int w=x>>6;
		int r=x&63;
		ull v=bit[w];

		if(r!=63)v&=(1ULL<<(r+1))-1;
		if(v)return(w<<6)+63-__builtin_clzll(v);

		for(--w;w>=0;w--){
			if(bit[w])return(w<<6)+63-__builtin_clzll(bit[w]);
		}

		return -1;
	}

	int next(int x)const{
		if(x>S)return -1;
		x=max(x,0);

		int w=x>>6;
		int r=x&63;
		ull v=bit[w]&(~0ULL<<r);

		if(v)return(w<<6)+__builtin_ctzll(v);

		for(++w;w<W;w++){
			if(bit[w]){
				int res=(w<<6)+__builtin_ctzll(bit[w]);
				return res<=S?res:-1;
			}
		}

		return -1;
	}

	ll count()const{
		ll res=0;
		for(ull x:bit)res+=__builtin_popcountll(x);
		return res;
	}

	bool any(int l,int r)const{
		if(l>r)return false;
		int x=next(l);
		return x!=-1&&x<=r;
	}

	int max_reachable()const{
		return prev(S);
	}
};
using DBSS=DynamicBitsetSubsetSum;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	ll t;
    cin >> t;
    while(t--){
        ll n,s;
        cin >> n >> s;
        DBSS dp(s);
        rep(i,0,n){
            ll a;
            cin >> a;
            dp.add(a);
        }
        cout << dp.max_reachable() << endl;
    }
}