#include <bits/stdc++.h>
using namespace std;
int T,N,A[1005], sum[1005];
bitset<1005> bs;
map< pair<int,int>, int> mp;
int dp (int n, int sum) {
if (mp.find(make_pair(n,sum)) != mp.end()) return mp[make_pair(n,sum)];
if (n == 0) return 0;
if (sum == 0 || sum == A[n]) return n;
return mp[make_pair(n,sum)] = max(dp(n-1,sum),dp(n-1,sum-A[n]));
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> T;
while (T--) {
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;
mp.clear();
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
428 ms |
4504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2076 ms |
28404 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2085 ms |
159772 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |