QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #733 | #425486 | #7403. Subset Sum | 5sb | qaqaq | Failed. | 2024-07-11 19:56:59 | 2024-07-11 19:57:00 |
詳細信息
Extra Test:
Accepted
time: 1573ms
memory: 4932kb
input:
1 20000 200000000 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:
200000000
result:
ok 1 number(s): "200000000"
| 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;
}