Submission #888384

#	Time	Username	Problem	Language	Result	Execution time	Memory
888384		pcc	Bootfall (IZhO17_bootfall)	C++14	28 / 100	553 ms	262144 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[mxn][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){
	if(sum&1)return false;
	if(!dp[sum>>1])return false;
	int tsum = sum+now;
	for(int i = 1;i<=n;i++){
		tsum -= arr[i];
		if(tsum&1)return false;
		if(tsum/2<now)return false;
		if(!del[i][tsum>>1])return false;
		tsum += arr[i];
	}
	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]]);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[i][j] = dp[j];
		for(int j = arr[i];j<C;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	vector<int> ans;
	for(int i = 1;i<C;i++){
		if(check(i))ans.push_back(i);
	}

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


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


	mod = 1e8+7;
	memset(dp,0,sizeof(dp));
	dp[0] = 1;
	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[i][j] = dp[j];
		for(int j = arr[i];j<C;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	for(auto &i:ans){
		if(check(i))ans2.push_back(i);
	}
	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: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35