Submission #1089417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089417		vjudge1	Kpart (eJOI21_kpart)	C++17	100 / 100	1065 ms	1376 KiB

Main

/*
	     author:khamzin
 	   Aibek aga is the best
	  created on 13.01.2024
	   20.10.2023 15:23:50
	   20.06.2024 16:38:22
                             		*/
#include <bits/stdc++.h>

#define EmirBey ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define rb rbegin()
#define re rend()
#define len(x) (int)x.size()
#define sz size()
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long
#define pii pair<int,int>

using namespace std;

const int N = 1e6+234;
const int INF = (int)1e9 + 1;
const int maxn = 2e5;
const int mod = 1e9+7;

int n,a[N],pref[N],dp[N];

void putin()
{
    cin>>n;
    set<int>ans;
    for(int i=1 ; i<=n ; i++){
    	cin>>a[i];
    	ans.insert(i);
    	pref[i]=pref[i-1]+a[i];
    }
    for(int i=0 ; i<=pref[n] ; i++)dp[i]=0;
    for(int i=1 ; i<=n ; i++){
    	for(int j=pref[n] ; j>=a[i] ; j--){
    		dp[j]=max(dp[j],dp[j-a[i]]);
    	}
    	dp[a[i]]=i;
    	for(int j=1 ; j<=i-1 ; j++){
    		int sum=pref[i]-pref[j-1];
    		if(sum%2==1 || dp[sum/2]<j){
    			ans.erase(i-j+1);
    		}
    	}
    }
    ans.erase(1);
    cout<<ans.size()<<' ';
    for(auto it:ans){
    	cout<<it<<' ';
    }
    cout<<'\n';
}
signed main() {
       	int tt=1;
       	cin>>tt;
       	while(tt--){
       		putin();
       	} 
       	
        

}

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