Submission #1100864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100864		Acanikolic	Kpart (eJOI21_kpart)	C++14	100 / 100	1829 ms	1408 KiB

Main

#include <bits/stdc++.h>  

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 1e5 + 10;
 
const int mod = 1e9 + 7;
 
const long long inf = 1e14;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 	
 	int tt;
 	cin >> tt;
 	while(tt--) {
 		int n;
 		cin >> n;
 		vector<int>a(n + 1),pref(n + 1);
 		for(int i = 1; i <= n; i++) {
 			cin >> a[i];
 			pref[i] = pref[i - 1] + a[i];
 		}
 		int mx = pref[n];
 		vector<bool>valid(n + 1,true);
 		vector<int>dp(mx + 1);
 		for(int i = 1; i <= n; i++) {
 			vector<int>new_dp = dp;
 			for(int j = a[i]; j <= mx; j++) {
 				new_dp[j] = max(new_dp[j],dp[j - a[i]]);
 			} 
 			new_dp[a[i]] = i;
 			dp = new_dp;
 			for(int j = i - 1; j >= 1; j--) {
 				int sum = pref[i] - pref[j - 1];
 				if(sum & 1 || dp[sum / 2] < j) valid[i - j + 1] = false;
 			}
 		}
 		vector<int>ans;
 		for(int i = 2; i <= n; i++) if(valid[i]) ans.pb(i);
 		cout << ans.size() << " ";
 		for(auto X : ans) cout << X << " ";
 		cout << "\n";
 	}
    return 0;
}

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