Submission #1129187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129187		ImperialALEN	Kpart (eJOI21_kpart)	C++20	100 / 100	1028 ms	2084 KiB

Main

#include <bits/stdc++.h> 
  
#define F first
#define S second 
#define ll long long
#define int long long
#define pb push_back
#define all(x) (x.begin(),x.end())
#define	ios	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define double long double


using namespace std;
 
const ll N = 3e5+7, INF = 1e14, inf = 1e9 , mod = 1e9+7;

int a[N];

bool good[N];

int dp[N];

int pref[N];

signed main(){
	ios;
	int tt;
	cin>>tt;
	while(tt--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			pref[i]=pref[i-1]+a[i];
		}
		for(int i=1;i<=n;i++){
			for(int x=pref[n];x>=1;x--){
				dp[x+a[i]]=max(dp[x+a[i]],dp[x]);
			}
			dp[a[i]]=i;
			for(int k=2;k<=i;k++){
				int sum=(pref[i]-pref[i-k]);
				if(sum%2==1 || dp[sum/2]<i-k+1)good[k]=1;
			}
		}
		vector<int>ans;
		for(int i=2;i<=n;i++){
			if(good[i]==0)ans.pb(i);
			good[i]=0;
		}
		cout<<ans.size()<<" ";
		for(auto to:ans)cout<<to<<" ";
		cout<<'\n';
		for(int i=1;i<=2e5;i++)dp[i]=0;
	}
}

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