Submission #1089456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089456		vjudge1	Kpart (eJOI21_kpart)	C++17	100 / 100	1120 ms	1552 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
#define accepted ios_base::sync_with_stdio(0);cin.tie(0);
#define Daulbekov signed
#define Makan main
#define int long long
#define double long double
#define pb push_back
#define F first
#define S second
const long long N=5e5+10;
const long long MOD=1e9+7;
const long long INF=2e18;
int binpow(int a,int b){
	a%=MOD;
	if(b==0)return 1;
	if(b%2)return binpow(a,b-1)*a%MOD;
	else {
		int res=binpow(a,b/2);
		return res*res%MOD;
	}
}
bool cmp(pair<pair<int,int>,int>a,pair<pair<int,int>,int>b){
	if(a.F.F/300!=b.F.F/300)return a.F.F/300<b.F.F/300;
	return a.F.S<b.F.S;
}
int dp[100005],a[1005],pref[1005],ans[1005];
Daulbekov Makan(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	accepted
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		pref[0]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			ans[i]=1;
			pref[i]=pref[i-1]+a[i];
		}
		for(int i=1;i<=n;i++){
			for(int x=100000;x>=a[i];x--){
				dp[x]=max(dp[x],dp[x-a[i]]);
			}
			dp[a[i]]=i;
			for(int k=2;k<=i;k++){
				int sum=pref[i]-pref[i-k];
				if(sum%2==0&&i-k+1<=dp[sum/2]);
				else ans[k]=0;
			}
		}
		int cnt=0;
		for(int i=2;i<=n;i++)cnt+=ans[i];
		cout<<cnt<<" ";
		for(int i=2;i<=n;i++)if(ans[i]==1)cout<<i<<" ";
		cout<<"\n";
		for(int i=1;i<=100000;i++)dp[i]=0;
	}
}

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