QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #732 | #425486 | #7403. Subset Sum | 5sb | qaqaq | Failed. | 2024-07-11 19:55:04 | 2024-07-11 19:55:04 |
詳細信息
Extra Test:
Accepted
time: 4ms
memory: 5008kb
input:
1 20000 400000000 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 ...
output:
399990000
result:
ok 1 number(s): "399990000"
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #425486 | #7403. Subset Sum | qaqaq | WA | 1562ms | 4960kb | C++14 | 827b | 2024-05-30 11:42:32 | 2024-07-11 20:10:26 |
answer
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define ll long long
using namespace std;
const int N=2e4+5;
const int M=1.7e6+5;
const int mod=1e9+7;
bitset<M*2>dp;
int n,c,x[N];
int main()
{
srand(114514);
int T;cin>>T;
while(T--){
dp.reset();int ans=0;
dp[M]=1;cin>>n>>c;
for(int i=0;i<n;i++)cin>>x[i];sort(x,x+n);
for(int i=0;i<n;i++)if(c>=x[i])c-=x[i],ans+=x[i],x[i]=-x[i];
if(c>20000||x[n-1]<0)
{
cout<<ans<<"\n";
continue;
}
dp[M]=1;
random_shuffle(x,x+n);
for(int i=0;i<n;i++)
if(x[i]<0)
dp|=dp>>(-x[i]);
else
dp|=dp<<x[i];
for(int i=c+M;i>=M;i--)
if(dp[i])
{
ans+=i-M;
break;
}
cout<<ans<<"\n";
}
return 0;
}