Submission #537799

#TimeUsernameProblemLanguageResultExecution timeMemory
537799hmm789Kpart (eJOI21_kpart)C++14
100 / 100
1656 ms193320 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--) {
		int n, sm;
		cin >> n;
		int a[n], pref[n+1];
		for(int i = 0; i < n; i++) cin >> a[i];
		pref[0] = 0;
		for(int i = 0; i < n; i++) pref[i+1] = pref[i] + a[i];
		sm = pref[n]/2;
		vector<int> ans;
		int dp[n][sm+1];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j <= sm; j++) {
				if(j == 0) dp[i][j] = i;
				else if(i == 0 && j == a[0]) dp[i][j] = i;
				else if(i == 0) dp[i][j] = -1;
				else if(j < a[i]) dp[i][j] = dp[i-1][j];
				else dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]]);
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n-i; j++) {
				sm = pref[j+i+1] - pref[j];
				if(sm % 2 == 1 || dp[j+i][sm/2] < j) goto ed;
			}
			ans.push_back(i+1);
			ed:;
		}
		cout << ans.size() << " ";
		for(int i : ans) cout << i << " ";
		cout << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...