Submission #497640

#TimeUsernameProblemLanguageResultExecution timeMemory
497640khangalBootfall (IZhO17_bootfall)C++14
100 / 100
382 ms12832 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; typedef long long ll; typedef double db; typedef vector<long long> vl; typedef pair<long long, long long > pl; const int N = 1e6 + 1; #define po pop_back #define pb push_back #define mk make_pair #define lw lower_bound #define up upper_bound #define ff first #define ss second #define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0); #define MOD 1000000007 #define MAX 1e18 #define MIN -1e18 #define per(i,a,b) for(ll i=b;i>=a;i--) #define con continue #define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628 // typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; // template< typename T> // using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ll n, m, ans, mid, mn, mx, cnt, sum, h1, h2, arr[3234567],arr1[1234567], sz, k, i, j, h, a, w, x, y, z,par[1234567]; bool used[1234567]; //ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123]; //vector<ll> edge[1234567]; //ll jump[22][223456]; //ll lvl[1234567]; //ll bit[1234567]; //ll timer; //ll st[1234567],endd[1234567]; //ll dp[5005][5005]; ll power(ll base, ll val, ll mod) { ll res = 1; while (val) { if (val % 2 == 1) { res = res * base; } base = base * base; base %= mod; res %= mod; val /= 2; } return res; } bool comp(pl x,pl y){ if(x.ff>y.ff)return true; return false; } ll find(ll x){ if(x==par[x])return x; else return par[x]=find(par[x]); } class A { public: static void funcA() { cin>>n; ll dp[1234567]; dp[0]=1; for(int i=1;i<=n;i++){ cin>>arr[i]; sum+=arr[i]; } for(int i=1;i<=n;i++){ for(int j=sum;j>=0;j--){ if(j-arr[i]>=0){ dp[j] += dp[j-arr[i]]; } } } bool ok[1234567]={0}; for(int i=1;i<=n;i++){ for(int j=arr[i];j<=sum;j++){ dp[j] -= dp[j-arr[i]]; } for(int j=1;j<=sum;j++){ ll k = sum - arr[i] + j; if(k%2==1 || dp[k/2]==0){ ok[j]=1; } } for(int j=sum;j>=arr[i];j--){ dp[j] += dp[j-arr[i]]; } } vl vec; for(int i=1;i<=sum;i++){ if(ok[i]==0)vec.pb(i); } if(sum%2==1 || dp[sum/2]==0)vec.clear(); cout<<vec.size()<<'\n'; for(auto u:vec){ cout<<u<<' '; } } }lol; void solve() { A::funcA(); } int main() { ll T = 1; //cin>>T; boost; while (T--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...