oj.uz

Submission #537447

# Submission time Handle Problem Language Result Execution time Memory
537447 2022-03-15T06:17:32 Z jamezzz Kpart (eJOI21_kpart) C++17
30 / 100
 2000 ms 460260 KB 
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf

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

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

int main(){
	sf("%d",&t);
	memset(old,-1,sizeof old);
	while(t--){
		sf("%d",&n);
		for(int i=1;i<=n;++i)sf("%d",&a[i]),p[i]=a[i]+p[i-1];
		memset(die,0,sizeof die);
		for(int i=1;i<=n;++i){
			for(int j=i;j<=n;++j){
				if(die[j-i+1])continue;
				if((p[j]-p[i-1])%2==1)die[j-i+1]=true;
				if(dp(j,(p[j]-p[i-1])/2)<i)die[j-i+1]=true;
			}
		}
		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");
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:18:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  sf("%d",&t);
      |    ^
Main.cpp:21:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   sf("%d",&n);
      |     ^
Main.cpp:22:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   for(int i=1;i<=n;++i)sf("%d",&a[i]),p[i]=a[i]+p[i-1];
      |                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 393984 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 394868 KB Output is correct
2 Correct 296 ms 397412 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 407736 KB Output is correct
2 Correct 1761 ms 425132 KB Output is correct
3 Correct 1933 ms 433712 KB Output is correct
4 Execution timed out 2114 ms 460260 KB Time limit exceeded
5 Halted 0 ms 0 KB -