제출 #1133994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133994		Agageldi	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1093 ms	464 KiB

bootfall

/*
ID: agageld1
LANG: C++17
TASK:
siuu
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 200005
#define pb push_back
#define ff first
#define ss second
#define sz(s) (int)s.size()

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, sum, t, pos[N];
vector <int> answer, v;
multiset <int> a;

int main (){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n;i++) {
		int x;
		cin >> x;
		sum += x;
		v.pb(x);
	}
	for(int i = 1; i <= 1000; i++) {
		sum += i;
		v.pb(i);
		bool tr = 0;
		for(auto j : v) {
			if((sum - j) % 2) tr = 1;
		}
		if(tr) {
			v.pop_back();
			sum -= i;
			continue;
		}
		for(int j = 0; j < sz(v); j++) {
			for(int m = 1; m <= sum; m++) {
				pos[m] = 0;
			}
			pos[0] = 1;
			sum -= v[j];
			for(int k = 0; k < sz(v); k++) {
				if(k == j) continue;
				for(int l = sum/2; l >= 0; l--) {
					if(pos[l]) pos[l + v[k]] = 1;
				}
			}
			sum += v[j];
			if(!pos[(sum - v[j]) / 2]) {
				tr = 1;
				break;
			}
		}
		if(!tr) answer.pb(i);
		v.pop_back();
		sum -= i;
	}
	cout << sz(answer) << '\n';
	for(auto i:answer) {
		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