Submission #537799

#	Time	Username	Problem	Language	Result	Execution time	Memory
537799		hmm789	Kpart (eJOI21_kpart)	C++14	100 / 100	1656 ms	193320 KiB

Main

#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';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70