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>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
bitset <271*271*2>dp[505], dp2[505];
int n, A[505];
const int os = 270 * 270;
bool chk(int a, int b){
if(os - a - b >= 0 && dp[n & 1][os - a - b])return 1;
if(os - a + b >= 0 && os - a + b <= 2 * os && dp[n & 1][os - a + b])return 1;
if(os + a - b >= 0 && os + a - b <= 2 * os && dp[n & 1][os + a - b])return 1;
if(os + a + b <= 2 * os && dp[n & 1][os + a + b])return 1;
return 0;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++)cin >> A[i];
//for(int i = 0; i <= 2 * os; i++)dp[0][i] = 0
dp[0][os] = dp2[n + 1][os] = 1;
for(int i = 1; i <= n; i++){
dp[i] |= (dp[i - 1] >> A[i]);
dp[i] |= (dp[i - 1] << A[i]);
}
for(int i = n; i >= 1; i--){
dp2[i] |= (dp2[i + 1] >> A[i]);
dp2[i] |= (dp2[i + 1] << A[i]);
}
if(!dp[n][os]){
cout << 0;
return;
}
set <int> s;
for(int i = 1; i <= os; i++)s.insert(i);
for(int i = 1; i <= n; i++){
/*
bitset <501*501*2> tmp = dp[i - 1], tmp2;
for(int j = 0; j <= os; j++){
if(dp2[i + 1][os - j] || dp2[i + 1][os + j]){
if(1)tmp2 |= (tmp >> j), tmp2 |= (tmp << j);
}
}
*/
bitset <271 * 271 * 2> tmp;
tmp[os] = 1;
for(int j = 1; j <= n; j++){
if(j == i)continue;
tmp = (tmp >> A[j]) | (tmp << A[j]);
}
for(int j = 0; j <= os; j++)if(!tmp[os - j] && !tmp[os + j])s.erase(j);
}
cout << (int)s.size() << '\n';
for(auto i : s)cout << i << ' ';
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message (stderr)
bootfall.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
66 | main(){
| ^~~~
# | 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... |