제출 #1283907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283907		urosk	Bootfall (IZhO17_bootfall)	C++20	0 / 100	1 ms	572 KiB

bootfall

#include "bits/stdc++.h"
#define ll long long
using namespace std;
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}

const int mod = 1000000007;
const int maxn = 505;
const int maxS = 250005;
int n;
int dp[maxS];
int a[maxn];
int ok[maxS];
// ok[x] = in how many rounds it is ok to add x
int 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;
		}
	}
	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<=s;new_player++){
			int cursum = s-a[i]+new_player;
			if(cursum%2==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<=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: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35