Submission #1283928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283928		urosk	Bootfall (IZhO17_bootfall)	C++20	100 / 100	441 ms	3476 KiB

bootfall

#include "bits/stdc++.h"

using namespace std;

const int mod = 1000000123;
const int maxn = 505;
const int maxS = 2*250005;
int n;
int dp[maxS];
int a[maxn];
int ok[maxS];
// ok[x] = in how many rounds it is ok to add x
signed main(){
	cin >> n;
	int s = 0;
	for(int i = 1;i<=n;i++) cin >> a[i],s+=a[i];
	dp[0] = 1;
	//Adding everything to knapsack
	for(int i = 1;i<=n;i++){
		for(int j = s;j>=a[i];j--){
			dp[j]+=dp[j-a[i]];
			if(dp[j]>=mod) dp[j]-=mod;
		}
	}
	if(s%2==1){
		cout<<0<<endl;
		return 0;
	}
	if(dp[s/2]==0){
		cout<<0<<endl;
		return 0;
	}
	for(int i = 1;i<=n;i++){
		//Deleting i from knapsack
		for(int j = a[i];j<=s;j++){
			dp[j]-=dp[j-a[i]];
			if(dp[j]<0) dp[j]+=mod;
		}
		int cursum = s-a[i];
		for(int new_player = 0;new_player<=2*s;new_player++){
			int cursum = s-a[i]+new_player;
			if(cursum%2==0&&cursum/2-new_player>=0&&dp[cursum/2-new_player]>0){
				ok[new_player]++;
			}
		}
		//Putting i back in knapsack
		for(int j = s;j>=a[i];j--){
			dp[j]+=dp[j-a[i]];
			if(dp[j]>=mod) dp[j]-=mod;
		}
	}
	vector<int> ans;
	for(int i = 1;i<=2*s;i++){
		if(ok[i]==n) ans.push_back(i);
	}
	cout<<ans.size()<<endl;
	for(int x : ans) cout<<x<< " ";
	cout<<endl;
	return 0;
}

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