Submission #164779

#	Time	Username	Problem	Language	Result	Execution time	Memory
164779		mosiashvililuka	Bootfall (IZhO17_bootfall)	C++14	44 / 100	1081 ms	5848 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f[509],p[509],pi,jm,pas[250009],pa;
bitset <250007> dp[177];
set <int> s;
set <int>::iterator it;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(c=1; c<=a; c++) cin>>f[c];
	if(a==1){
		cout<<0;
		return 0;
	}
	for(c=1; c<=a; c++){
		s.insert(f[c]);
	}
	for(it=s.begin(); it!=s.end(); it++){
		pi++;
		p[pi]=(*it);
	}
	d=0;
	for(c=1; c<=a; c++) d+=f[c];
	e=d;
	jm=e;
	for(c=2; c<=a; c++){
		if(f[c]%2!=f[c-1]%2){
			cout<<0;
			return 0;
		}
	}
/*	for(c=1; c<=pi; c++) cout<<p[c]<<" ";
	cout<<endl<<endl;*/
	for(c=1; c<=pi+1; c++){
//	    cout<<jm<<endl;
	    dp[c][0]=1;
	    e=0;
		for(d=1; d<=a; d++){
    		if(f[d]==p[c]&&e==0){
			   e=1;
			   continue;
			}
			//if(c==1) cout<<d<<" ";
			dp[c]=dp[c]|(dp[c]<<f[d]);
		}
		dp[c][0]=0;
//		dp[c][jm-p[c]]=0;
	}
//	cout<<dp[1][400]<<endl;
/*	cout<<endl;
	for(c=1; c<=14; c++){
	    cout<<c<<" "<<dp[1][c]<<endl;
	}*/
//	cout<<dp[4][5]<<endl;
	if(f[1]%2==0) d=2; else d=1;
	for(c=d; c<=jm; c+=2){
		pi++;p[pi]=c;
		jm+=c;
		e=0;
		for(d=1; d<=pi; d++){
			if(d==pi){
			if((jm-p[d])%2==1||dp[pi][(jm-p[d])/2]==0){
//			    if(c==600) cout<<jm<<" "<<p[d]<<" "<<d<<endl;
//			    if(c==3) cout<<jm<<" "<<p[d]<<" "<<d<<endl;
				e=1;break;
			}
			}else{
			if((jm-p[d])%2==1||dp[d][(jm-p[d])/2]==0){
//			    if(c==600) cout<<jm<<" "<<p[d]<<" "<<d<<endl;
//			    if(c==3) cout<<jm<<" "<<p[d]<<" "<<d<<endl;
				e=1;break;
			}
			}
		}
		if(e==0){
			pa++;
			pas[pa]=c;
		}
		jm-=c;
		pi--;
	}
	cout<<pa<<endl;
	for(c=1; c<=pa; c++) cout<<pas[c]<<" ";
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35