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 GCC optimize("Ofast")
#pragma comment(linker, "/stack:200000000")
// #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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;
vector < int > ans;
bitset < 500 * 500 + 1 > dp;
void sol(){
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;
}
for(short int i = 1; i <= n; i++){
dp &= 0, dp[0] = 1, s = 0;
for(short int j = 1; j <= n; j++)
if(i != j)
dp |= (dp << a[j]), s += a[j];
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++;
}
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for(int x : ans) cout << x << ' ';
}
signed main(){
ios
sol();
// slow();
// stress();
}
Compilation message (stderr)
bootfall.cpp:2: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
2 | #pragma comment(linker, "/stack:200000000")
|
bootfall.cpp:5:71: warning: bad option '-fprofile-values' to pragma 'optimize' [-Wpragmas]
5 | #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
| ^
bootfall.cpp:10:41: warning: bad option '-ffunction-sections' to pragma 'optimize' [-Wpragmas]
10 | #pragma GCC optimize("function-sections")
| ^
bootfall.cpp:11:37: warning: bad option '-fdata-sections' to pragma 'optimize' [-Wpragmas]
11 | #pragma GCC optimize("data-sections")
| ^
bootfall.cpp:12:51: warning: bad option '-fbranch-target-load-optimize' to pragma 'optimize' [-Wpragmas]
12 | #pragma GCC optimize("branch-target-load-optimize")
| ^
bootfall.cpp:13:52: warning: bad option '-fbranch-target-load-optimize2' to pragma 'optimize' [-Wpragmas]
13 | #pragma GCC optimize("branch-target-load-optimize2")
| ^
bootfall.cpp:14:40: warning: bad option '-fbtr-bb-exclusive' to pragma 'optimize' [-Wpragmas]
14 | #pragma GCC optimize("btr-bb-exclusive")
| ^
bootfall.cpp:75:10: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
75 | void sol(){
| ^
bootfall.cpp:75:10: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
bootfall.cpp:75:10: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
bootfall.cpp:75:10: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
bootfall.cpp:75:10: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
bootfall.cpp:75:10: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
bootfall.cpp: In function 'void sol()':
bootfall.cpp:89:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | while(j < ans.size()){
| ~~^~~~~~~~~~~~
bootfall.cpp:91:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(j < ans.size()) swap(ans[j], ans[ans.size() - 1]);
| ~~^~~~~~~~~~~~
bootfall.cpp: At global scope:
bootfall.cpp:104:13: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
104 | signed main(){
| ^
bootfall.cpp:104:13: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
bootfall.cpp:104:13: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
bootfall.cpp:104:13: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
bootfall.cpp:104:13: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
bootfall.cpp:104:13: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
# | 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... |