Submission #537488

#	Time	Username	Problem	Language	Result	Execution time	Memory
537488		hmm789	Kpart (eJOI21_kpart)	C++14	30 / 100	2117 ms	782296 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;
		cin >> n;
		int a[n], pref[n+1], sm;
		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;
		bool dp[n][n][sm+1];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j <= sm; j++) {
				if(j == 0 || j == a[i]) dp[i][i][j] = 1;
				else dp[i][i][j] = 0;
			}
			for(int j = i+1; j < n; j++) {
				for(int k = 0; k <= sm; k++) {
					if(dp[i][j-1][k] == 1 || (a[j] <= k && dp[i][j-1][k-a[j]] == 1)) dp[i][j][k] = 1;
					else dp[i][j][k] = 0;
				}
			}
		}
		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][j+i][sm/2] == 0) {
					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: 0 / 70