# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
537472 |
2022-03-15T06:37:29 Z |
joelau |
Kpart (eJOI21_kpart) |
C++14 |
|
2000 ms |
787108 KB |
#include <bits/stdc++.h>
using namespace std;
int T,N,A[1005], sum[1005], memo[1005][100005], memo2[1005][100005], TC;
bitset<1005> bs;
unordered_map<int,int> mp;
int dp (int n, int sum) {
if (n == 0) return 0;
if (sum == 0 || sum == A[n]) return n;
if (memo2[n][sum] == TC) return memo[n][sum];
memo2[n][sum] = TC;
return memo[n][sum] = max(dp(n-1,sum),dp(n-1,sum-A[n]));
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
memset(memo,-1,sizeof(memo));
memset(memo2,-1,sizeof(memo2));
cin >> T;
for (TC = 0; TC < T; ++TC) {
cin >> N;
A[0] = sum[0] = 0;
for (int i = 1; i <= N; ++i) {
cin >> A[i];
sum[i] = sum[i-1] + A[i];
}
bs.reset();
for (int i = 1; i <= N; ++i) bs[i] = 1;
for (int i = 1; i <= N; ++i) for (int j = 1; j <= i; ++j) {
int total = sum[i] - sum[j-1];
if (total % 2 == 1 || dp(i,total/2) < j) bs[i-j+1] = 0;
}
cout << bs.count();
for (int i = 1; i <= N; ++i) if (bs[i]) cout << ' ' << i;
cout << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
397 ms |
787040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
391 ms |
787056 KB |
Output is correct |
2 |
Correct |
719 ms |
787068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1850 ms |
787108 KB |
Output is correct |
2 |
Execution timed out |
2140 ms |
787048 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |