# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
166764 | abil | Bootfall (IZhO17_bootfall) | C++14 | 3 ms | 424 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long
using namespace std;
const int N = (1e6 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);
int a[N], f[N];
set<int > s;
bitset< N > b;
main()
{
int n, sum = 0;
scanf("%d", &n);
for(int i = 1;i <= n; i++){
scanf("%d", &a[i]);
}
f[0] = 1;
for(int i = 1;i <= n; i++){
for(int j = sum + a[i];j >= a[i]; j--){
f[j] += f[j - a[i]];
if(f[j] >= mod){
f[j] -= mod;
}
}
sum += a[i];
}
if(!f[sum / 2] || sum & 1){
cout << 0;
return 0;
}
for(int i = 1;i <= sum; i++){
b[i] = 1;
}
//for(int i = 1;i <= sum; i++){
//cout << f[i] << " ";
//}
//cout << endl;
for(int i = 1;i <= n; i++){
for(int j = a[i];j <= sum; j++){
f[j] -= f[j - a[i]];
//if(f[j] < 0){
//f[j] += mod;
//}
}
//for(int j = 1;j <= sum; j++){
//cout << f[j] << " ";
//}
//cout << endl;
for(int j = 1;j <= sum; j++){
if((sum - a[i] + j) & 1 || !f[(sum - a[i] + j) / 2]){
b[j] = 0;
}
}
for(int j = sum;j >= a[i]; j--){
f[j] += f[j - a[i]];
//if(f[j] >= mod){
//f[j] -= mod;
//}
}
}
cout << b.count() << endl;
for(int i = 1;i <= sum; i++){
if(b[i]){
cout << i << " ";
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |