Submission #1128253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128253		ImperialALEN	Kpart (eJOI21_kpart)	C++20	0 / 100	2094 ms	680 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);	
 
using namespace std;
  
const ll N = 1001+9, INF = 1e18 , inf = 1e9 , mod = 1e9+7;

int a[N];
int pref[N];

map<int,int>dp;

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];
		}
		if(n<=120){
			vector<int>ans;
			for(int len=1;len<=n;len++){
				bool ok=0;
				vector<int>v;
				for(int l=1;l+len-1<=n;l++){
					int r=l+len-1;
					if((pref[r]-pref[l-1])%2==1){
						ok=1;
						break;
					}
					if(l==1){
						for(int i=l;i<=r;i++)v.pb(a[i]);
					}else{
						v.erase(v.begin());
						v.pb(a[r]);
					}
//					cout<<l<<" "<<r<<endl;
					bool yes=0;
					for(auto to:v){
						for(int x=pref[r]-pref[l-1];x>=1;x--){
							if(x-to>=0){
								dp[x]=max(dp[x],dp[x-to]+to);
								if(dp[x]==(pref[r]-pref[l-1])/2){
									yes=1;
									break;
								}
							}
						}
						if(yes)break;
					}
//					cout<<yes<<endl;
					dp.clear();
					if(!yes){
						ok=1;
						break;
					}
				}
				if(ok)continue;
				else ans.pb(len);
			}
			cout<<ans.size()<<" ";
			for(auto to:ans)cout<<to<<" ";
			cout<<'\n';
		}
	}
}

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