#include <bits/stdc++.h>
#define first x
#define second y
using namespace std;
const int INF = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> a(n);
for(int i=0; i<n; i++) {
cin >> a[i];
}
vector<int> pref(n);
pref[0] = a[0];
for(int i=1; i<n; i++) {
pref[i] = pref[i-1] + a[i];
}
vector<vector<int>> dp(n, vector<int>(pref[n-1] / 2 + 2, -1));
for(int i=0; i<n; i++) {
int lim = dp[0].size();
for(int x=1; x<lim; x++) {
if(x==a[i]) {
dp[i][x] = i;
} else if(i>0)
{
dp[i][x] = dp[i-1][x];
if(x-a[i]>0) {
dp[i][x] = max(dp[i][x], dp[i-1][x-a[i]]);
}
}
}
}
vector<int> ans;
for(int k=2; k<=n; k++) {
bool flag = true;
for(int i=0; i+k<=n; i++) {
int curSum = pref[i+k-1];
if(i>0) {
curSum -= pref[i-1];
}
if(curSum%2==1||dp[i+k-1][curSum/2]<i) {
flag = false;
break;
}
}
if(flag) {
ans.push_back(k);
}
}
cout << ans.size() << " ";
for(int k: ans) {
cout << k << " ";
}
cout << "\n";
}
return 0;
}
/*
3
3 1 1
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
1260 KB |
Output is correct |
2 |
Correct |
50 ms |
3336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
223 ms |
13292 KB |
Output is correct |
2 |
Correct |
614 ms |
29684 KB |
Output is correct |
3 |
Correct |
715 ms |
37896 KB |
Output is correct |
4 |
Correct |
1285 ms |
64532 KB |
Output is correct |
5 |
Execution timed out |
2041 ms |
161816 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |