Submission #537451

#	Time	Username	Problem	Language	Result	Execution time	Memory
537451		jamezzz	Kpart (eJOI21_kpart)	C++17	30 / 100	2096 ms	133416 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

int t,n,a[1005],p[1005],memo[1005][100005],old[1005][100005],die[1005];

inline int dp(int i,int v){
	if(a[i]==v)return i;
	if(v<0||i==0)return 0;
	if(old[i][v]==t+1)return memo[i][v];
	old[i][v]=t+1;
	return memo[i][v]=max(dp(i-1,v),dp(i-1,v-a[i]));
}

int main(){
	t=rd();
	while(t--){
		n=rd();
		for(int i=1;i<=n;++i)a[i]=rd(),p[i]=a[i]+p[i-1];
		memset(die,0,sizeof die);
		for(int k=1;k<=n;++k){
			for(int i=1;i+k-1<=n;++i){
				int j=i+k-1;
				if(die[k])break;
				if(((p[j]-p[i-1])&1)==1)die[k]=1;
				if(dp(j,(p[j]-p[i-1])/2)<i)die[k]=1;
			}
		}
		int cnt=0;
		for(int i=1;i<=n;++i)if(!die[i])++cnt;
		pf("%d ",cnt);
		for(int i=1;i<=n;++i)if(!die[i])pf("%d ",i);
		pf("\n");
	}
}

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