Submission #673420

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
673420	2022-12-20T15:18:00 Z	pragmatist	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1000 ms	460 KB

bootfall

/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/

#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")

#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)5e2 + 7; // make sure this is right
const int M = 1e4 + 5;
const int inf = (int)1e9;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)998244353; // make sure this is right

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, a[N], dp[M];
bool ans[N];

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

int sub(int x, int y) {
	x -= y;
	if(x < 0) x += MOD;
	return x;
}

void add(int x) {
	for(int i = M - 1; i >= x; --i) {
		dp[i] = sum(dp[i], dp[i - x]);
	}
}

void del(int x) {
	for(int i = x; i < M; ++i) {
		dp[i] = sub(dp[i], dp[i - x]);
	}
}

void solve() {
	cin >> n;
	dp[0] = 1;
	int sum = 0;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	    add(a[i]);
		sum += a[i];
	}
	n++;        
	vector<int> ans;
	for(int x = 1; x < M; ++x) {
		a[n] = x;
		add(x); 
		bool ok = 1;
		for(int i = 1; i <= n && ok; ++i) {
			del(a[i]);

			int need = (sum + x - a[i]) >> 1;
			if((sum + x - a[i]) & 1) {
				ok = 0;
			} else {                
				ok &= (dp[need] > 0);				
			}
			add(a[i]);			
		}
		if(ok) ans.pb(x);
		del(x);
	}
	
	cout << sz(ans) << nl;
	for(auto x : ans) cout << x << ' ';
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);                                                         

	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	520 ms	340 KB	Output is correct
2	Correct	304 ms	340 KB	Output is correct
3	Correct	360 ms	340 KB	Output is correct
4	Correct	255 ms	348 KB	Output is correct
5	Correct	304 ms	340 KB	Output is correct
6	Correct	261 ms	348 KB	Output is correct
7	Correct	257 ms	340 KB	Output is correct
8	Correct	298 ms	340 KB	Output is correct
9	Correct	268 ms	340 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	520 ms	340 KB	Output is correct
2	Correct	304 ms	340 KB	Output is correct
3	Correct	360 ms	340 KB	Output is correct
4	Correct	255 ms	348 KB	Output is correct
5	Correct	304 ms	340 KB	Output is correct
6	Correct	261 ms	348 KB	Output is correct
7	Correct	257 ms	340 KB	Output is correct
8	Correct	298 ms	340 KB	Output is correct
9	Correct	268 ms	340 KB	Output is correct
10	Correct	273 ms	460 KB	Output is correct
11	Correct	374 ms	344 KB	Output is correct
12	Correct	263 ms	340 KB	Output is correct
13	Correct	260 ms	340 KB	Output is correct
14	Correct	347 ms	340 KB	Output is correct
15	Correct	351 ms	340 KB	Output is correct
16	Correct	385 ms	340 KB	Output is correct
17	Correct	302 ms	344 KB	Output is correct
18	Correct	332 ms	348 KB	Output is correct
19	Correct	308 ms	340 KB	Output is correct
20	Correct	300 ms	324 KB	Output is correct

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	520 ms	340 KB	Output is correct
2	Correct	304 ms	340 KB	Output is correct
3	Correct	360 ms	340 KB	Output is correct
4	Correct	255 ms	348 KB	Output is correct
5	Correct	304 ms	340 KB	Output is correct
6	Correct	261 ms	348 KB	Output is correct
7	Correct	257 ms	340 KB	Output is correct
8	Correct	298 ms	340 KB	Output is correct
9	Correct	268 ms	340 KB	Output is correct
10	Correct	273 ms	460 KB	Output is correct
11	Correct	374 ms	344 KB	Output is correct
12	Correct	263 ms	340 KB	Output is correct
13	Correct	260 ms	340 KB	Output is correct
14	Correct	347 ms	340 KB	Output is correct
15	Correct	351 ms	340 KB	Output is correct
16	Correct	385 ms	340 KB	Output is correct
17	Correct	302 ms	344 KB	Output is correct
18	Correct	332 ms	348 KB	Output is correct
19	Correct	308 ms	340 KB	Output is correct
20	Correct	300 ms	324 KB	Output is correct
21	Execution timed out	1093 ms	348 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	520 ms	340 KB	Output is correct
2	Correct	304 ms	340 KB	Output is correct
3	Correct	360 ms	340 KB	Output is correct
4	Correct	255 ms	348 KB	Output is correct
5	Correct	304 ms	340 KB	Output is correct
6	Correct	261 ms	348 KB	Output is correct
7	Correct	257 ms	340 KB	Output is correct
8	Correct	298 ms	340 KB	Output is correct
9	Correct	268 ms	340 KB	Output is correct
10	Correct	273 ms	460 KB	Output is correct
11	Correct	374 ms	344 KB	Output is correct
12	Correct	263 ms	340 KB	Output is correct
13	Correct	260 ms	340 KB	Output is correct
14	Correct	347 ms	340 KB	Output is correct
15	Correct	351 ms	340 KB	Output is correct
16	Correct	385 ms	340 KB	Output is correct
17	Correct	302 ms	344 KB	Output is correct
18	Correct	332 ms	348 KB	Output is correct
19	Correct	308 ms	340 KB	Output is correct
20	Correct	300 ms	324 KB	Output is correct
21	Execution timed out	1093 ms	348 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	520 ms	340 KB	Output is correct
2	Correct	304 ms	340 KB	Output is correct
3	Correct	360 ms	340 KB	Output is correct
4	Correct	255 ms	348 KB	Output is correct
5	Correct	304 ms	340 KB	Output is correct
6	Correct	261 ms	348 KB	Output is correct
7	Correct	257 ms	340 KB	Output is correct
8	Correct	298 ms	340 KB	Output is correct
9	Correct	268 ms	340 KB	Output is correct
10	Correct	273 ms	460 KB	Output is correct
11	Correct	374 ms	344 KB	Output is correct
12	Correct	263 ms	340 KB	Output is correct
13	Correct	260 ms	340 KB	Output is correct
14	Correct	347 ms	340 KB	Output is correct
15	Correct	351 ms	340 KB	Output is correct
16	Correct	385 ms	340 KB	Output is correct
17	Correct	302 ms	344 KB	Output is correct
18	Correct	332 ms	348 KB	Output is correct
19	Correct	308 ms	340 KB	Output is correct
20	Correct	300 ms	324 KB	Output is correct
21	Execution timed out	1093 ms	348 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	520 ms	340 KB	Output is correct
2	Correct	304 ms	340 KB	Output is correct
3	Correct	360 ms	340 KB	Output is correct
4	Correct	255 ms	348 KB	Output is correct
5	Correct	304 ms	340 KB	Output is correct
6	Correct	261 ms	348 KB	Output is correct
7	Correct	257 ms	340 KB	Output is correct
8	Correct	298 ms	340 KB	Output is correct
9	Correct	268 ms	340 KB	Output is correct
10	Correct	273 ms	460 KB	Output is correct
11	Correct	374 ms	344 KB	Output is correct
12	Correct	263 ms	340 KB	Output is correct
13	Correct	260 ms	340 KB	Output is correct
14	Correct	347 ms	340 KB	Output is correct
15	Correct	351 ms	340 KB	Output is correct
16	Correct	385 ms	340 KB	Output is correct
17	Correct	302 ms	344 KB	Output is correct
18	Correct	332 ms	348 KB	Output is correct
19	Correct	308 ms	340 KB	Output is correct
20	Correct	300 ms	324 KB	Output is correct
21	Execution timed out	1093 ms	348 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Submission #673420

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0