# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
602927 | 2022-07-23T12:44:25 Z | berr | Kpart (eJOI21_kpart) | C++17 | 2000 ms | 130712 KB |
#include <bits/stdc++.h> using namespace std; int knp[1005][100015]; vector<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 | 4 ms | 724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 2516 KB | Output is correct |
2 | Correct | 81 ms | 7160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 384 ms | 27280 KB | Output is correct |
2 | Correct | 1000 ms | 61364 KB | Output is correct |
3 | Correct | 1123 ms | 78044 KB | Output is correct |
4 | Execution timed out | 2060 ms | 130712 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |