# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1112935 | adiyer | Bootfall (IZhO17_bootfall) | C++17 | 136 ms | 3060 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.
#pragma optimize ("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
using namespace std;
typedef int ll;
const int N = 5e2;
const int MAX = N * N;
short int n;
short int a[N];
int s;
int dp[MAX + 1];
vector < int > ans;
void sol(){
cin >> n, dp[0] = 1;
for(int i = 1; i <= MAX; i++) ans.pb(i);
for(short int i = 0; i < n; i++){
cin >> a[i], s += a[i];
for(ll j = MAX; j >= a[i]; j--) dp[j] += dp[j - a[i]];
}
if(s % 2 || dp[s / 2] == 0){
cout << "0\n";
return;
}
for(short int i = 0; i < n; i++){
s -= a[i];
for(int j = a[i]; j <= MAX; j++) dp[j] -= dp[j - a[i]];
int j = 0;
while(j < ans.size()){
if(s < ans[j] || (s - ans[j]) % 2 || !dp[(s - ans[j]) / 2]){
if(j < ans.size()) swap(ans[j], ans[ans.size() - 1]);
ans.pop_back();
}
else{
j++;
}
}
s += a[i];
for(int j = MAX; j >= a[i]; j--) dp[j] += dp[j - a[i]];
}
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for(int x : ans) cout << x << ' ';
}
signed main(){
ios
sol();
// slow();
// stress();
}
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... |