oj.uz

Submission #168368

# Submission time Handle Problem Language Result Execution time Memory
168368 2019-12-12T19:30:14 Z mosiashvililuka Bootfall (IZhO17_bootfall) C++14
0 / 100
 2 ms 376 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -