Submission #888386

#	Time	Username	Problem	Language	Result	Execution time	Memory
888386		pcc	Bootfall (IZhO17_bootfall)	C++14	44 / 100	594 ms	3676 KiB

bootfall

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 510;
const int C = mxn*mxn;
int mod = 998244353;
int arr[mxn];
int dp[C];
int del[C];
int n;
int sum = 0;

inline ll mad(int a,int b){
	a += b;
	return a>=mod?a-mod:a;
}
inline ll mub(int a,int b){
	return mad(a,mod-b);
}

inline bool check(int now,int tsum){
	if(sum&1)return false;
	if(!dp[sum>>1])return false;
	if(tsum&1)return false;
	if(tsum/2<now)return false;
	if(!del[tsum>>1])return false;
	return true;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		cin>>arr[i];
		sum += arr[i];
		for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	}
	vector<int> ans,ans2;
	for(int i = 1;i<=sum;i++)ans.push_back(i);
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[j] = dp[j];
		for(int j = arr[i];j<C;j++)del[j] = mub(del[j],del[j-arr[i]]);
		for(auto &j:ans){
			if(check(j,sum-arr[i]+j))ans2.push_back(j);
		}
		swap(ans,ans2);
		ans2.clear();
	}

	memset(dp,0,sizeof(dp));
	dp[0] = 1;
	mod = 1e9+7;
	for(int i = 1;i<=n;i++)for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[j] = dp[j];
		for(int j = arr[i];j<C;j++)del[j] = mub(del[j],del[j-arr[i]]);
		for(auto &j:ans){
			if(check(j,sum-arr[i]+j))ans2.push_back(j);
		}
		swap(ans,ans2);
		ans2.clear();
	}

	memset(dp,0,sizeof(dp));
	dp[0] = 1;
	mod = 712271227;
	for(int i = 1;i<=n;i++)for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[j] = dp[j];
		for(int j = arr[i];j<C;j++)del[j] = mub(del[j],del[j-arr[i]]);
		for(auto &j:ans){
			if(check(j,sum-arr[i]+j))ans2.push_back(j);
		}
		swap(ans,ans2);
		ans2.clear();
	}



	/*
	for(int i = 0;i<=10;i++)cout<<dp[i]<<' ';cout<<endl;
	cout<<sum<<endl;
	cout<<endl;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=10;j++)cout<<del[i][j]<<' ';cout<<endl;
	}
   */

	cout<<ans.size()<<'\n';
	for(auto &i:ans)cout<<i<<' ';
	return 0;
}

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