# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1115439 | vjudge1 | Bootfall (IZhO17_bootfall) | C++17 | 148 ms | 3268 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 mxN = 5e2;
const int mxSm = mxN * mxN;
int dp[mxSm + 1];
vector<int> ans;
int a[mxN];
int s;
void solve() {
int N;
cin >> N;
for (int i = 1; i <= mxSm; i ++) {
ans.pb(i);
}
dp[0] = 1;
for (int i = 0; i < N; i ++) {
cin >> a[i];
for (int j = mxSm; j >= a[i]; j --) {
dp[j] += dp[j - a[i]];
}
s += a[i];
}
if (s % 2 || dp[s / 2] == 0) {
cout << "0\n";
return;
}
for (int i = 0; i < N; i ++) {
s -= a[i];
for (int j = a[i]; j <= mxSm; j ++) {
dp[j] -= dp[j - a[i]];
}
int j = 0;
while (j<(int)ans.size()){
if (s < ans[j] || (s - ans[j]) % 2 || !dp[(s - ans[j]) / 2]) {
if (j < (int)ans.size()) {
swap(ans[j], ans[(int)ans.size()-1]);
}
ans.pop_back();
} else {
j ++;
}
}
s += a[i];
for (int j = mxSm; j >= a[i]; j --) {
dp[j] += dp[j - a[i]];
}
}
sort(begin(ans),end(ans));
cout << ans.size() << "\n";
for (int i : ans) {
cout << i << ' ';
}
}
signed main() {
ios
solve();
}
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... |