oj.uz

Submission #682443

# Submission time Handle Problem Language Result Execution time Memory
682443 2023-01-16T08:56:09 Z iskhakkutbilim Bootfall (IZhO17_bootfall) C++14
13 / 100
 1000 ms 15272 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 <= S; 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 = S; 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 83 ms 15036 KB Output is correct
2 Correct 98 ms 15112 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 87 ms 15192 KB Output is correct
5 Correct 153 ms 15124 KB Output is correct
6 Correct 125 ms 15136 KB Output is correct
7 Correct 97 ms 15056 KB Output is correct
8 Correct 155 ms 15092 KB Output is correct
9 Correct 0 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15036 KB Output is correct
2 Correct 98 ms 15112 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 87 ms 15192 KB Output is correct
5 Correct 153 ms 15124 KB Output is correct
6 Correct 125 ms 15136 KB Output is correct
7 Correct 97 ms 15056 KB Output is correct
8 Correct 155 ms 15092 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 616 ms 15084 KB Output is correct
11 Correct 580 ms 15272 KB Output is correct
12 Correct 580 ms 15048 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 506 ms 15108 KB Output is correct
15 Correct 539 ms 15084 KB Output is correct
16 Correct 582 ms 15028 KB Output is correct
17 Correct 258 ms 15168 KB Output is correct
18 Correct 408 ms 15120 KB Output is correct
19 Correct 449 ms 15048 KB Output is correct
20 Correct 577 ms 15048 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15036 KB Output is correct
2 Correct 98 ms 15112 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 87 ms 15192 KB Output is correct
5 Correct 153 ms 15124 KB Output is correct
6 Correct 125 ms 15136 KB Output is correct
7 Correct 97 ms 15056 KB Output is correct
8 Correct 155 ms 15092 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 616 ms 15084 KB Output is correct
11 Correct 580 ms 15272 KB Output is correct
12 Correct 580 ms 15048 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 506 ms 15108 KB Output is correct
15 Correct 539 ms 15084 KB Output is correct
16 Correct 582 ms 15028 KB Output is correct
17 Correct 258 ms 15168 KB Output is correct
18 Correct 408 ms 15120 KB Output is correct
19 Correct 449 ms 15048 KB Output is correct
20 Correct 577 ms 15048 KB Output is correct
21 Execution timed out 1098 ms 15124 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15036 KB Output is correct
2 Correct 98 ms 15112 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 87 ms 15192 KB Output is correct
5 Correct 153 ms 15124 KB Output is correct
6 Correct 125 ms 15136 KB Output is correct
7 Correct 97 ms 15056 KB Output is correct
8 Correct 155 ms 15092 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 616 ms 15084 KB Output is correct
11 Correct 580 ms 15272 KB Output is correct
12 Correct 580 ms 15048 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 506 ms 15108 KB Output is correct
15 Correct 539 ms 15084 KB Output is correct
16 Correct 582 ms 15028 KB Output is correct
17 Correct 258 ms 15168 KB Output is correct
18 Correct 408 ms 15120 KB Output is correct
19 Correct 449 ms 15048 KB Output is correct
20 Correct 577 ms 15048 KB Output is correct
21 Execution timed out 1098 ms 15124 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15036 KB Output is correct
2 Correct 98 ms 15112 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 87 ms 15192 KB Output is correct
5 Correct 153 ms 15124 KB Output is correct
6 Correct 125 ms 15136 KB Output is correct
7 Correct 97 ms 15056 KB Output is correct
8 Correct 155 ms 15092 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 616 ms 15084 KB Output is correct
11 Correct 580 ms 15272 KB Output is correct
12 Correct 580 ms 15048 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 506 ms 15108 KB Output is correct
15 Correct 539 ms 15084 KB Output is correct
16 Correct 582 ms 15028 KB Output is correct
17 Correct 258 ms 15168 KB Output is correct
18 Correct 408 ms 15120 KB Output is correct
19 Correct 449 ms 15048 KB Output is correct
20 Correct 577 ms 15048 KB Output is correct
21 Execution timed out 1098 ms 15124 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15036 KB Output is correct
2 Correct 98 ms 15112 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 87 ms 15192 KB Output is correct
5 Correct 153 ms 15124 KB Output is correct
6 Correct 125 ms 15136 KB Output is correct
7 Correct 97 ms 15056 KB Output is correct
8 Correct 155 ms 15092 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 616 ms 15084 KB Output is correct
11 Correct 580 ms 15272 KB Output is correct
12 Correct 580 ms 15048 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 506 ms 15108 KB Output is correct
15 Correct 539 ms 15084 KB Output is correct
16 Correct 582 ms 15028 KB Output is correct
17 Correct 258 ms 15168 KB Output is correct
18 Correct 408 ms 15120 KB Output is correct
19 Correct 449 ms 15048 KB Output is correct
20 Correct 577 ms 15048 KB Output is correct
21 Execution timed out 1098 ms 15124 KB Time limit exceeded
22 Halted 0 ms 0 KB -