# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
499817 | 2021-12-29T15:36:35 Z | luka1234 | Bootfall (IZhO17_bootfall) | C++14 | 7 ms | 204 KB |
#include<bits/stdc++.h> #define ll long long #define ff first #define ss second using namespace std; ll findmin(ll a[],ll n){ ll sum=0; for(ll k=1;k<=n;k++){ sum+=a[k]; } bool dp[n+1][sum+1]; for(ll k=1;k<=n;k++){ dp[k][0]=1; } for(ll k=1;k<=sum;k++){ dp[0][k]=0; } for(ll i=1;i<=n;i++){ for(ll j=1;j<=sum;j++){ dp[i][j]=dp[i-1][j]; if(dp[i][j]==1) continue; if(j>=a[i]) dp[i][j]=dp[i-1][j-a[i]]; else dp[i][j]=0; } } ll diff=1e9; for(ll k=sum/2;k>=0;k--){ if(dp[n][k]==1){ diff=sum-k*2; break; } } return diff; } int main(){ ll n; cin>>n; ll a[n+1]; ll a1[n+2]; ll a2[n+2]; for(ll k=1;k<=n;k++){ cin>>a[k]; a1[k+1]=a[k]; a2[k+1]=a[k]; } vector<ll> ans; for(ll k=1;k<=500;k++){ a1[1]=k; a2[1]=k; ll ind=0; for(ll i=1;i<=n+1;i++){ a2[i]=0; ll diff=findmin(a2,n+1); a2[i]=a1[i]; if(diff!=0){ ind=1; break; } } if(ind==0) ans.push_back(k); } cout<<ans.size()<<"\n"; for(ll k=0;k<ans.size();k++) cout<<ans[k]<<' '; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 2 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 7 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 2 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 7 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 2 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 7 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 2 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 7 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 2 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 7 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 2 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 7 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |