oj.uz

Submission #537471

# Submission time Handle Problem Language Result Execution time Memory
537471 2022-03-15T06:36:13 Z jamezzz Kpart (eJOI21_kpart) C++17
100 / 100
 1059 ms 195916 KB 
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf

#define getchar_unlocked getchar

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],dp[1005][50005],die[1005];

int main(){
	t=rd();
	for(int i=1;i<=1000;++i)dp[i-1][0]=i;
	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 i=1;i<=n;++i){
			for(int v=1;v<=50000;++v){
				dp[i][v]=max(dp[i-1][v],dp[i-1][v-a[i]]);
			}
		}
		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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 10324 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 17496 KB Output is correct
2 Correct 120 ms 27188 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 53664 KB Output is correct
2 Correct 401 ms 77920 KB Output is correct
3 Correct 435 ms 87520 KB Output is correct
4 Correct 573 ms 112660 KB Output is correct
5 Correct 852 ms 172168 KB Output is correct
6 Correct 1059 ms 193264 KB Output is correct
7 Correct 973 ms 195916 KB Output is correct