Submission #888373

#	Time	Username	Problem	Language	Result	Execution time	Memory
888373		pcc	Bootfall (IZhO17_bootfall)	C++14	28 / 100	212 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 = 550;
const int mod = 998244353;
int arr[mxn];
int dp[mxn*mxn];
int del[mxn][mxn*mxn];
int n;
int sum = 0;

inline ll mad(ll a,ll b){
	a += b;
	return a>=mod?a-mod:a;
}
inline ll mub(ll a,ll 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 = mxn*mxn-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<mxn*mxn;j++)del[i][j] = dp[j];
		for(int j = arr[i];j<mxn*mxn;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	vector<int> ans;
	for(int i = 1;i<mxn*mxn;i++){
		if(check(i))ans.push_back(i);
	}

	/*
	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