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 + 11;
const int MAX = 1e6;
short int n;
short int a[N];
int s, sz, j;
vector < int > ans;
bitset < 500 * 500 + 3 > dp;
signed main(){
ios
cin >> n, dp[0] = 1;
for(ll i = 1; i <= 500 * 500; i++) ans.pb(i);
for(ll i = 1; i <= n; i++) cin >> a[i], dp |= (dp << a[i]), s += a[i];
if(s % 2 || dp[s / 2] == 0){
cout << "0\n";
return 0;
}
for(short int i = 1; i <= n; i++){
dp &= 0, dp[0] = 1, s = 0;
for(j = 1; j <= n; j++)
if(i != j)
dp |= (dp << a[j]), s += a[j];
j = 0, sz = ans.size();
while(j < sz){
while(j < sz && (s < ans[j] || (s - ans[j]) % 2 || !dp[(s - ans[j]) / 2])){
swap(ans[j], ans[sz - 1]);
ans.pop_back();
sz--;
}
j++;
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for(int x : ans) cout << x << ' ';
}
Compilation message (stderr)
bootfall.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
1 | #pragma optimize ("g",on)
|
# | 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... |