Submission #638235

#	Time	Username	Problem	Language	Result	Execution time	Memory
638235		Tekor	Kpart (eJOI21_kpart)	C++17	30 / 100	2086 ms	992 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define en '\n'
void boos() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int N = 1e3 + 100,M = 1e5 + 10;
int n,cnt[N],dp[M],a[N],pr[N];
void solve() {
	int m = 0;
	cin >> n;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
		m += a[i];
		pr[i] = m;
		cnt[i] = 0;
	}
	for(int i = 0;i <= m;i++)dp[i] = n + 1;
	for(int i = n;i >= 1;i--) {
		dp[0] = i;
		for(int j = m;j >= 1;j--) {
			if(j >= a[i])dp[j] = min(dp[j],dp[j - a[i]]);
			if(dp[j] != n + 1 && j % 2 == 0 && dp[j / 2] <= dp[j] && j == pr[dp[j]] - pr[i - 1])cnt[dp[j] - i + 1]++;
			//cout << dp[j] << " ";
		}
		//cout << en;
		//cout << cnt[4] << " " << cnt[6] << en;
	}
	vector <int> ans;
	for(int i = 2;i <= n;i++) {
		if(cnt[i] == n - i + 1)ans.pb(i);
	}
	cout << ans.size() << " ";
	for(auto to : ans)cout << to << " ";
	cout << en;
}
int main() {
	boos();
	int ttt;
	cin >> ttt;
	while(ttt--)solve();
}

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