Submission #168368

#	Time	Username	Problem	Language	Result	Execution time	Memory
168368		mosiashvililuka	Bootfall (IZhO17_bootfall)	C++14	0 / 100	2 ms	376 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,f[509],mod1=1000000007,mod2=1000000009,mas[250009],sm,p[250009],pi;
pair <long long, long long> dp[509],dpp[509];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(b=1; b<=a; b++) cin>>f[b];
	for(b=1; b<=a; b++) sm+=f[b];
	for(b=2; b<=a; b++){
		if(f[b]%2!=f[b-1]%2){
			cout<<0;
			return 0;
		}
	}
	if(sm%2==1){
		cout<<0;
		return 0;
	}
	dp[0].first=1;dp[0].second=1;
	for(b=1; b<=a; b++){
		for(d=sm; d>=f[b]; d--){
			dp[d].first+=dp[d-f[b]].first;
			dp[d].second+=dp[d-f[b]].second;
			dp[d].first%=mod1;
			dp[d].second%=mod2;
		}
	}
	cout<<dp[2].first<<endl;
	for(b=1; b<=a; b++){
		for(d=sm; d>=f[b]; d--){
			dp[d].first-=dp[d-f[b]].first-mod1;
			dp[d].second-=dp[d-f[b]].second-mod2;
			dp[d].first%=mod1;
			dp[d].second%=mod2;
		}
		if(dp[sm/2].first==0&&dp[sm/2].second==0) continue;
		d=f[1]%2;
		if(d==0) d=2;
		for( ; d<=sm; d+=2){
			for(c=a; c>=1; c--){
				e=(sm+d-f[c])/2;
				if(dp[e].first==0&&dp[e].second==0) break;
			}
			if(c==0) mas[d]++;
		}
		for(d=sm; d>=f[b]; d--){
			dp[d].first+=dp[d-f[b]].first;
			dp[d].second+=dp[d-f[b]].second;
			dp[d].first%=mod1;
			dp[d].second%=mod2;
		}
	}
	for(b=1; b<=sm; b++){
		if(mas[b]==a){
			pi++;
			p[pi]=b;
		}
	}
	cout<<pi<<endl;
	for(b=1; b<=pi; b++) cout<<p[b]<<" ";
	return 0;
}

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