QOJ.ac
QOJ
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #549 | #211618 | #7403. Subset Sum | 5sb | SolitaryDream | Success! | 2024-02-29 19:10:11 | 2024-02-29 19:10:11 |
Details
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 | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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;
}
}
}
}