# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
602929 | 2022-07-23T12:45:47 Z | berr | Kpart (eJOI21_kpart) | C++17 | 2000 ms | 386020 KB |
#include <bits/stdc++.h> using namespace std; int knp[1005][100015]; int pre[1005], a[1005]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int t; cin>>t; int p=0; while(t--) { int n; cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; pre[i]=pre[i-1]+a[i]; } for(int i=0; i<=pre[n]; i++) knp[0][i]=0; for(int i=1; i<=n; i++) { for(int l=pre[n-1]-a[i]; l>0; l--) { knp[i][a[i]+l] = max(knp[i-1][a[i]+l], knp[i-1][l]); } knp[i][a[i]]=i; for (int j = a[i]-1; j > 0; j--) knp[i][j] = knp[i - 1][j]; } vector<int> ans; for (int i=2; i<=n; i++) { int flag=1; for (int j=1; j<=n-i+1; j++) { int sum = pre[j+i-1]; sum-=pre[j-1]; if (sum%2==1||knp[j+i-1][sum/2]<j) flag = 0; } if (flag == 1) ans.push_back(i); } cout<<ans.size()<<" "; for(auto i: ans) cout<<i<<" "; cout<<"\n"; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 2604 KB | Output is correct |
2 | Correct | 25 ms | 7016 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 104 ms | 27248 KB | Output is correct |
2 | Correct | 291 ms | 61352 KB | Output is correct |
3 | Correct | 337 ms | 78076 KB | Output is correct |
4 | Correct | 627 ms | 130692 KB | Output is correct |
5 | Correct | 1434 ms | 320684 KB | Output is correct |
6 | Execution timed out | 2050 ms | 386020 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |