Submission #925552

#	Time	Username	Problem	Language	Result	Execution time	Memory
925552		WanWan	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1075 ms	5272 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
#define int long long 

const int MOD1 = (int)1e9 + 7;
const int MOD2 = 998244353;
const int MOD3 = (int)1e9 + 9;
int n;
int A[505];
int ways[505*505][3];
int cnt[505*500];
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	vector<int> MODS={MOD1,MOD2,MOD3};
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>A[i];
		sum+=A[i];
	}
	ways[0][0]=1;
	ways[0][1]=1;
	ways[0][2]=1;

	for(int i=1;i<=n;i++){
		for(int j=sum;j>=0;j--){
			for(int k=0;k<=2;k++){
				if(j-A[i]>=0)ways[j][k]=(ways[j][k]+ways[j-A[i]][k])%MODS[k];
			}
		}
	}
	unordered_set<int>os;
	if(sum % 2 == 1){
		return cout << 0,0;
	}
	if(ways[sum/2][0] == 0 && ways[sum/2][1] == 0 && ways[sum/2][2] == 0){
		return cout << 0,0;
	}

	for(int i=1;i<=n;i++){ // remove this
		unordered_set<int>os;
		for(int j=0;j<=sum;j++){
			for(int k=0;k<=2;k++){
				if(j-A[i]>=0)ways[j][k]=(ways[j][k]-ways[j-A[i]][k]+MODS[k])%MODS[k];
			}
			if(ways[j][0] != 0 && ways[j][1] != 0 && ways[j][2] != 0){
				int diff=abs(j-((sum-A[i])-j));
				os.insert(diff);
			}
			
		}
		for(auto x:os){
			if(x>=0)cnt[x]++;
		}
		for(int j=sum;j>=0;j--){
			for(int k=0;k<=2;k++){
				if(j-A[i]>=0)ways[j][k]=(ways[j][k]+ways[j-A[i]][k])%MODS[k];
			}
		}
	}
	vector<int>out;
	for(int j=1;j<=sum;j++){

		if(cnt[j] == n){
			out.push_back(j);
		}
	}
	cout<<out.size()<<"\n";
	for(auto x:out)cout<<x<<" ";

}	

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