#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 + 1);
pref[0] = 0;
for(int i=0; i<n; i++) {
pref[i+1] = pref[i] + a[i];
}
vector<vector<int>> dp(n, vector<int>(pref[n] / 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] - pref[i];
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 |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
1260 KB |
Output is correct |
2 |
Correct |
52 ms |
3352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
221 ms |
13268 KB |
Output is correct |
2 |
Correct |
624 ms |
29712 KB |
Output is correct |
3 |
Correct |
706 ms |
37836 KB |
Output is correct |
4 |
Correct |
1285 ms |
64432 KB |
Output is correct |
5 |
Execution timed out |
2082 ms |
161896 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |