제출 #840924

#제출 시각아이디문제언어결과실행 시간메모리
840924peraKpart (eJOI21_kpart)C++17
90 / 100
909 ms916 KiB
#include<bits/stdc++.h>
using namespace std;

//#define int long long

const int N = 2e5 + 1;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t = 1;cin >> t;
	while(t --){
		int n;cin >> n;
		vector<int> a(n + 1) , p(n + 1) , ls(n + 1) , ans;
		for(int i = 1;i <= n;i ++){
			cin >> a[i];
			p[i] = p[i - 1] + a[i];
			ls[i] = 1;
		}
		int X = p[n] / 2;
		vector<int> dp(X);
		for(int i = 1;i <= n;i ++){
			auto ndp = dp;
			dp[a[i]] = i;
			for(int j = X;j > a[i];j --){
				dp[j] = max(dp[j] , ndp[j - a[i]]);
			}
			for(int k = 1;k <= i;k ++){
				ls[i - k + 1] &= ((p[i] - p[k - 1]) % 2 == 0 && dp[(p[i] - p[k - 1]) / 2] >= k);
			}
		}
		cout << accumulate(ls.begin() , ls.end() , 0) << endl;
		for(int i = 1;i <= n;i ++){
			if(ls[i] == 1) cout << i << " ";
		}
		cout << endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...