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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define ft first
#define sc second
using namespace std;
const int mod=1e9+7,INF=1e17;
int sum,dp[500005],res[500005],a[505];
void fun(int x){
for(int i=sum;i>=0;i--){
dp[i+x]+=dp[i];
}
}
void fun2(int x){
for(int i=0;i<=sum;i++){
dp[i+x]-=dp[i];
}
}
main(){
int n;
cin>> n;
dp[0]=1;
for(int i=1;i<=n;i++){
cin >> a[i];
fun(a[i]);
sum+=a[i];
}
if(sum%2!=0 || dp[sum/2]==0){
cout << 0;
return 0;
}
for(int i=1;i<=n;i++){
fun2(a[i]);
sum-=a[i];
for(int j=sum/2;j<=sum;j++){
if(dp[j]!=0 && j*2>sum){
res[j*2-sum]++;
}
}
sum+=a[i];
fun(a[i]);
}
vector<int> ans;
for(int i=1;i<=sum;i++){
if(res[i]==n){
ans.push_back(i);
}
}
cout << ans.size() << endl;
for(auto x : ans){
cout << x << " ";
}
}
Compilation message (stderr)
bootfall.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
22 | 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... |