Submission #169702

#	Time	Username	Problem	Language	Result	Execution time	Memory
169702		Dovran	Bootfall (IZhO17_bootfall)	C++11	13 / 100	3 ms	380 KiB

bootfall

#include <bits/stdc++.h>
#define N 1000009
#define pii pair <int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long

using namespace std;

int n, m, v[N], sum, vis[N], ism;
int an[N];
vector<int>ans;

int main(){
	cin >> n;
	for(int i=1; i<=n; i++)
		cin>>v[i], sum+=v[i];
	
	vis[0] = 1;
	
	for(int i = 1; i <= n;i++)
		for(int j = sum; j >= 0; j--)
			vis[j+v[i]] += vis[j];
			
	if(sum%2==1 or vis[sum/2]==0)
		return cout<<0, 0;
	
	for(int i = 1; i <= n; i++){
		for(int j = v[i]; j <= sum;j++)
			vis[j] -= vis[j - v[i]];
		for(int j = 1; j < sum; j++){
			if(an[j]<i-1)
				continue;
			ism = sum - v[i] + j;
			if(ism % 2 == 0 and ism / 2 - j >= 0 and vis[ism / 2 - j]>0 and vis[ism / 2]>0)
				an[j]++;
//			cout<<v[i]<<' '<<j<<' '<<an[j]<<' '<<ism<<endl;
		}
		for(int j = sum; j >= v[i]; j--)
			vis[j] += vis[j - v[i]];
	}
	for(int i = 1; i <= sum; i++)
		if(an[i] == n) ans.pb(i);
	cout<< ans.size() <<'\n';
	for(auto i : ans)
		cout<< i <<' ';
}

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