Submission #36241

#	Time	Username	Problem	Language	Result	Execution time	Memory
36241		touristk2000	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1000 ms	4860 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int inf = (500*500) / 2;
int n;
int a[511];
int b[505*505];
int van[505*505];

void ins(int val){
	for(int i = inf; i >= 0; i --){
	    if(i < val) break;
		b[i] += b[i - val];
		if(b[i] >= mod) b[i] -= mod;
	}
}

void ers(int val){
	for(int i = 0; i <= inf; i ++){
	    if(i + val > inf) break;
		b[val + i] -= b[i];
		if(b[val + i] < 0) b[val + i] += mod;
	}
}

int main(){		
    //freopen("bootfall.in","r",stdin);
    //freopen("bootfall.out","w",stdout);
	b[0] = 1;
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	} 
	int s = 0;
	for(int i = 1; i <= n; i ++){
	    s += a[i];
		ins(a[i]);
	}
	if(s % 2 == 1){
	    cout << 0;
		return 0;
	}
	else if(b[s >> 1] == 0){
	    cout << 0;
	    return 0;
	}
	for(int i = 1; i <= n; i ++){
		ers(a[i]);
		for(int j = 0; j <= inf; j ++){
			if(s - a[i] - j - j >= 0){
				if(b[j] > 0){
					van[s - a[i] - j - j] ++;
				}
			}
		}
		ins(a[i]);
	}
	
	vector<int> res;
	for(int i = 0; i < inf + inf; i ++){
		if(van[i] == n) res.push_back(i);
	}
	cout << res.size() << endl;
	for(int i = 0; i < res.size(); i ++) cout << res[i] << " ";
    return 0;	
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < res.size(); i ++) cout << res[i] << " ";
                   ^

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