oj.uz

Submission #682436

# Submission time Handle Problem Language Result Execution time Memory
682436 2023-01-16T08:51:55 Z iskhakkutbilim Bootfall (IZhO17_bootfall) C++14
13 / 100
 41 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 500;
const int S =2*500 * 500;
int dp[S+1];
main(){
	int n; cin >> n;
	vector<int> a(n);
	int sum = 0, even = 0, odd = 0;
	for(int i = 0;i < n; i++){
		cin >> a[i];
		odd+= (a[i]%2==1);
		even+= (a[i]%2==0);
		sum+= a[i];
	}
	dp[0] = 1;
	for(int i = 0;i < n; i++){
		for(int s = sum/2; s >= 0; s--){
			if(s >= a[i]){
				dp[s] = max(dp[s], dp[s-a[i]]);
			}
		}
	}
	if((even > 0 and odd > 0) or sum%2 or !dp[sum/2]){
		cout << 0;
		return 0;
	}
	set<int> can;
	for(int tima = 1; tima <= 1000; tima++){
		sum+= tima;
		int ok = 1;
		for(int i = 0;i < a.size(); i++){
			if((sum-a[i])%2==1){
				ok = 0;
				break;
			}
		}
		if(ok) can.insert(tima);
		sum-= tima;
	}
	for(int i = 0;i < n; i++){
		for(int s = sum; s >= 1; s--) dp[s] = 0;
		for(int j = 0;j < n; j++){
			if(i == j) continue;
			for(int s = sum-a[i]; s >= 0; s--){
				if(s>=a[j]) dp[s] = max(dp[s], dp[s-a[j]]);
			}
		}
		vector<int> del;
		for(int tima : can){
			if(!dp[(sum-a[i]+tima) / 2]) del.push_back(tima);
		}
		for(int x : del) can.erase(x);
	}
	cout << can.size() << '\n';
	for(int x : can) cout << x << ' ';
	return 0;
}

Compilation message

bootfall.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main(){
      | ^~~~
bootfall.cpp: In function 'int main()':
bootfall.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int i = 0;i < a.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 6 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 7 ms 212 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 6 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 7 ms 212 KB Output is correct
21 Incorrect 41 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 6 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 7 ms 212 KB Output is correct
21 Incorrect 41 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 6 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 7 ms 212 KB Output is correct
21 Incorrect 41 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 6 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 7 ms 212 KB Output is correct
21 Incorrect 41 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -