Submission #580876

#	Time	Username	Problem	Language	Result	Execution time	Memory
580876		penguin133	Kpart (eJOI21_kpart)	C++14	30 / 100	2072 ms	1400 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pi pair<int, int> 
#define pii pair<int, pair<int, int> >
int P[200005], P2[200005], A[200005], S[200005];
int n;
bool dp[2][100005];
bool X[1005][1005];
void solve(){
	memset(X, 0, sizeof(X));
	cin >> n;
	int ans = 0;
	for(int i=1;i<=n;i++)cin >> A[i], ans += A[i], P[i] = P[i-1] + A[i];
	for(int i=1;i<=n;i++){
		for(int j=0;j<=1;j++)for(int k=0;k<=ans;k++)dp[j][k] = 0;
		dp[(i-1)%2][0] = 1;
		for(int j=i;j<=n;j++){
			int x = j % 2;
			for(int k=0;k<=ans;k++){
				if(k >= A[j])dp[x][k] = (dp[1-x][k-A[j]] | dp[1-x][k]);
				else dp[x][k] = dp[1-x][k];
			}
			if((P[j]  - P[i-1])%2 == 0 && dp[j%2][(P[j] - P[i-1])/2])X[i][j] = 1;
		}
	}
	vector<int>v;
	for(int i=1;i<=n;i++){
		int flag = 1;
		for(int j=1;j<=n-i+1;j++)if(!X[j][j+i-1])flag = 0;
		if(flag)v.push_back(i);
	}
	cout << v.size() << " ";
	for(auto i : v)cout << i << " ";
	cout << '\n';
	
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

Main.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      | ^~~~

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