oj.uz

Submission #634435

# Submission time Handle Problem Language Result Execution time Memory
634435 2022-08-24T11:51:37 Z uncripted Kpart (eJOI21_kpart) C++11
100 / 100
 715 ms 824 KB 
#include<bits/stdc++.h>
using namespace std;	

int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int a[n+1];
		int pas[n+1];
		int sum=0;
		for(int i=1; i<=n; i++){
			cin>>a[i];
			pas[i]=1;
			sum+=a[i];
		
		}
		int las[100005]={};
		sum/=2;
		for(int i=1; i<=n; i++){
			for(int j=sum-a[i]; j>0; j--){
				las[j+a[i]]=max(las[j], las[j+a[i]]);
			}
			if(a[i]<=sum){
				las[a[i]]=i;	
			}
			
			int s=0;
			for(int j=i; j>=1; j--){
				s+=a[j];
				if(s%2==1){
					pas[i-j+1]=0;
					continue;
				}
				if(las[s/2]<j){
					pas[i-j+1]=0;
				}
			}
		}
		int p=0;
		for(int i=2; i<=n; i++){
			if(pas[i]==1){
				p++;
			}
		}
		cout<<p<<" ";
		for(int i=2; i<=n; i++){
			if(pas[i]==1){
				cout<<i<<" ";
			}
		}
		cout<<endl;
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 10 ms 596 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 596 KB Output is correct
2 Correct 105 ms 676 KB Output is correct
3 Correct 132 ms 676 KB Output is correct
4 Correct 216 ms 688 KB Output is correct
5 Correct 497 ms 808 KB Output is correct
6 Correct 715 ms 824 KB Output is correct
7 Correct 624 ms 700 KB Output is correct