QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #549 | #211618 | #7403. Subset Sum | 5sb | SolitaryDream | Success! | 2024-02-29 19:10:11 | 2024-02-29 19:10:11 |
详细
Extra Test:
Wrong Answer
time: 38ms
memory: 4016kb
input:
1666 12 120000 19999 19999 19999 19999 19999 19999 20000 20000 20000 20000 20000 20000 12 120000 19999 19999 19999 19999 19999 19999 20000 20000 20000 20000 20000 20000 12 120000 19999 19999 19999 19999 19999 19999 20000 20000 20000 20000 20000 20000 12 120000 19999 19999 19999 19999 19999 19999 200...
output:
120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000 120000...
result:
wrong answer 332nd numbers differ - expected: '120000', found: '119999'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #211618 | #7403. Subset Sum | SolitaryDream# | WA | 82ms | 4060kb | C++17 | 1.0kb | 2023-10-12 19:27:28 | 2024-10-14 07:57:36 |
answer
#include<bits/stdc++.h>
using namespace std;
const int S=1e5,N=S*2+10;
bitset<N> f;
int n,a[20001],c,T;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&c);
// n=20000,c=2e8;
for(int i=1;i<=n;i++)
// a[i]=rand()%20000+1;
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int w=0;
for(int i=1;i<=n;i++)
if(c>=a[i])
{
c-=a[i];
w+=a[i];
a[i]=-a[i];
}
if(a[n]<0)
{
printf("%d\n",w);
continue;
}
random_shuffle(a+1,a+n+1);
f.reset();
f.set(S);
for(int i=1;i<=n;i++)
if(a[i]<0)
f|=f>>-a[i];
else
f|=f<<a[i];
for(int i=min(c,S);i>=0;i--)
{
if(f.test(i+S))
{
printf("%d\n",i+w);
break;
}
}
}
}