# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
337941 | kutbilim_one | Bootfall (IZhO17_bootfall) | C++14 | 428 ms | 5992 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.
/** kutbilim.one **/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
#define endl '\n'
/*
ifstream in("test.txt");
#define cin in */
const int MAX = 500*500+1;
int dp[MAX] = {1};
vector<int> used(MAX, 1);
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n);
int sum = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
for(int x = sum; x >= 0; x--)
dp[x+a[i]] += dp[x];
sum += a[i];
}
if(sum%2 == 1 || dp[sum/2] == 0) return cout << 0, 0;
for(int ex = 0; ex < n; ex++){
int left = sum-a[ex];
for(int x = 0; x <= left; x++)
dp[x + a[ex]] -= dp[x];
for(int right = 0; right <= MAX; right++)
if((left+right)%2 == 1 || dp[(left+right)/2] == 0) used[right] = 0;
for(int x = left; x >= 0; x--)
dp[x + a[ex]] += dp[x];
}
vector<int> res;
for(int i = 0; i <= MAX; i++){
if(used[i]) res.push_back(i);
}
cout << res.size() << endl;
for(auto i : res) cout << i << " ";
return 0;
}
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... |