# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
545561 | 2022-04-04T21:23:51 Z | MilosMilutinovic | Bootfall (IZhO17_bootfall) | C++14 | 16 ms | 4300 KB |
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;} const int md=1e9+7; int n,a[505],dp[505*505],cc[505*505],ndp[505*505]; void chkadd(int&x,int y){x+=y; if(x>md) x-=md;} void chksub(int&x,int y){x-=y; if(x<0) x+=md;} int main(){ scanf("%d",&n); dp[0]=1; int s=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); for(int j=505*505-1;j>=a[i];j--) chkadd(dp[j],dp[j-a[i]]); s+=a[i]; } if((s&1)||!dp[s/2]){printf("0"); return 0;} for(int i=1;i<=n;i++){ for(int j=0;j<505*505;j++) ndp[j]=dp[j]; for(int j=0;j<505*505-a[i];j++) chksub(ndp[j+a[i]],ndp[j]); for(int j=0;j<505*505;j++){ int ns=s-a[i]+j; if(ns%2==0&&ndp[ns/2-j]) cc[j]++; } } vector<int> ans; for(int i=0;i<505*505;i++) if(cc[i]==n) ans.pb(i); printf("%d\n",ans.size()); for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 4300 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 4300 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 4300 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 4300 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 4300 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 4300 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |