답안 #682436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682436	2023-01-16T08:51:55 Z	iskhakkutbilim	Bootfall (IZhO17_bootfall)	C++14	13 / 100	41 ms	340 KB

bootfall

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #682436

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