# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
91180 | 2018-12-26T13:06:59 Z | emil_physmath | Bootfall (IZhO17_bootfall) | C++14 | 1000 ms | 123088 KB |
#include <iostream> #include <stdio.h> #include <unordered_set> #include <cstring> #include <vector> #include <cmath> #include <set> using namespace std; const int MAXN=500, MAXSUM=500*500; int a[MAXN+1]; bool dp[MAXN][MAXSUM+1]; vector<int> AllPossSums(int arr[], int n); int main() { int n, sum=0; cin>>n; set<int> mods; for (int i=0; i<n; i++) { scanf("%d", a+i); mods.insert(a[i]%2); sum+=a[i]; } if (mods.size()>1) { cout<<"0\n"; return 0; } if (*(mods.begin())) if (n%2) { cout<<"0\n"; return 0; } vector<int> curSums; curSums=AllPossSums(a, n); bool f=false; for (int i=0; i<curSums.size(); i++) if (curSums[i]*2==sum) { f=true; break; } if (!f) { cout<<"0\n"; return 0; } unordered_set<int> ans; for (int i=0; i<n; i++) { // #i doesn't play. sum-=a[i]; swap(a[i], a[n-1]); curSums=AllPossSums(a, n-1); unordered_set<int> curAns; for (int j=0; j<curSums.size(); j++) curAns.insert(abs(sum-curSums[j]-curSums[j])); if (!i) { ans=curAns; swap(a[i], a[n-1]); sum+=a[i]; continue; } unordered_set<int> temp; for (auto it=curAns.begin(); it!=curAns.end(); it++) if (ans.find(*it)!=ans.end()) { temp.insert(*it); //ans.erase(*it); //curAns.erase(*it); } ans=temp; swap(a[i], a[n-1]); sum+=a[i]; } cout<<ans.size()<<'\n'; set<int> ansOut(ans.begin(), ans.end()); for (auto it=ansOut.begin(); it!=ansOut.end(); it++) cout<<*it<<' '; cout<<endl; char I; cin >> I; return 0; } vector<int> AllPossSums(int arr[], int n) { int sum=0; for (int i=0; i<n; i++) sum+=arr[i]; memset(dp, 0, sizeof(dp)); for (int i=0; i<=n; i++) dp[i][0]=true; for (int i=1; i<=n; i++) { dp[i][arr[i-1]]=true; for (int j=1; j<=sum; j++) { if (dp[i-1][j]==true) { dp[i][j]=true; dp[i][j+arr[i-1]]=true; } } } vector<int> res; for (int j=0; j<=sum; j++) if (dp[n][j]==true) res.push_back(j); return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 221 ms | 122616 KB | Output is correct |
2 | Correct | 289 ms | 122748 KB | Output is correct |
3 | Correct | 99 ms | 122828 KB | Output is correct |
4 | Correct | 222 ms | 122868 KB | Output is correct |
5 | Correct | 471 ms | 123016 KB | Output is correct |
6 | Correct | 344 ms | 123016 KB | Output is correct |
7 | Correct | 285 ms | 123016 KB | Output is correct |
8 | Correct | 477 ms | 123088 KB | Output is correct |
9 | Correct | 2 ms | 123088 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 221 ms | 122616 KB | Output is correct |
2 | Correct | 289 ms | 122748 KB | Output is correct |
3 | Correct | 99 ms | 122828 KB | Output is correct |
4 | Correct | 222 ms | 122868 KB | Output is correct |
5 | Correct | 471 ms | 123016 KB | Output is correct |
6 | Correct | 344 ms | 123016 KB | Output is correct |
7 | Correct | 285 ms | 123016 KB | Output is correct |
8 | Correct | 477 ms | 123088 KB | Output is correct |
9 | Correct | 2 ms | 123088 KB | Output is correct |
10 | Correct | 871 ms | 123088 KB | Output is correct |
11 | Execution timed out | 1037 ms | 123088 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 221 ms | 122616 KB | Output is correct |
2 | Correct | 289 ms | 122748 KB | Output is correct |
3 | Correct | 99 ms | 122828 KB | Output is correct |
4 | Correct | 222 ms | 122868 KB | Output is correct |
5 | Correct | 471 ms | 123016 KB | Output is correct |
6 | Correct | 344 ms | 123016 KB | Output is correct |
7 | Correct | 285 ms | 123016 KB | Output is correct |
8 | Correct | 477 ms | 123088 KB | Output is correct |
9 | Correct | 2 ms | 123088 KB | Output is correct |
10 | Correct | 871 ms | 123088 KB | Output is correct |
11 | Execution timed out | 1037 ms | 123088 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 221 ms | 122616 KB | Output is correct |
2 | Correct | 289 ms | 122748 KB | Output is correct |
3 | Correct | 99 ms | 122828 KB | Output is correct |
4 | Correct | 222 ms | 122868 KB | Output is correct |
5 | Correct | 471 ms | 123016 KB | Output is correct |
6 | Correct | 344 ms | 123016 KB | Output is correct |
7 | Correct | 285 ms | 123016 KB | Output is correct |
8 | Correct | 477 ms | 123088 KB | Output is correct |
9 | Correct | 2 ms | 123088 KB | Output is correct |
10 | Correct | 871 ms | 123088 KB | Output is correct |
11 | Execution timed out | 1037 ms | 123088 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 221 ms | 122616 KB | Output is correct |
2 | Correct | 289 ms | 122748 KB | Output is correct |
3 | Correct | 99 ms | 122828 KB | Output is correct |
4 | Correct | 222 ms | 122868 KB | Output is correct |
5 | Correct | 471 ms | 123016 KB | Output is correct |
6 | Correct | 344 ms | 123016 KB | Output is correct |
7 | Correct | 285 ms | 123016 KB | Output is correct |
8 | Correct | 477 ms | 123088 KB | Output is correct |
9 | Correct | 2 ms | 123088 KB | Output is correct |
10 | Correct | 871 ms | 123088 KB | Output is correct |
11 | Execution timed out | 1037 ms | 123088 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 221 ms | 122616 KB | Output is correct |
2 | Correct | 289 ms | 122748 KB | Output is correct |
3 | Correct | 99 ms | 122828 KB | Output is correct |
4 | Correct | 222 ms | 122868 KB | Output is correct |
5 | Correct | 471 ms | 123016 KB | Output is correct |
6 | Correct | 344 ms | 123016 KB | Output is correct |
7 | Correct | 285 ms | 123016 KB | Output is correct |
8 | Correct | 477 ms | 123088 KB | Output is correct |
9 | Correct | 2 ms | 123088 KB | Output is correct |
10 | Correct | 871 ms | 123088 KB | Output is correct |
11 | Execution timed out | 1037 ms | 123088 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |