oj.uz

Submission #62785

# Submission time Handle Problem Language Result Execution time Memory
62785 2018-07-30T03:59:22 Z Tenuun Bootfall (IZhO17_bootfall) C++17
13 / 100
 1000 ms 2072 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
int n, a[500], res[250001];

bool s[250001];

void check(){
	s[0]=true;
	for(int i=0; i<n; i++){
		for(int j=250000; j>=0; j--){
			if(!s[j]) continue;
			s[j+a[i]]=true;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tot=0;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i];
		tot+=a[i];
	}
	memset(res, 0, sizeof res);
	memset(s, 0, sizeof s);
	check();
	if(tot%2 || !s[tot/2]){
		return cout << 0, 0;
	}
	int tmp;
	for(int i=0; i<n; i++){
		tmp=a[i];
		a[i]=0;
		memset(s, 0, sizeof s);
		check();
		tot-=tmp;
		for(int j=1; j<=tot; j++){
			if((tot+j)%2) continue;
			if(s[(tot+j)/2]){
				res[j]++;
			}
		}
		tot+=tmp;
		a[i]=tmp;
	}
	vector<int>res;
	for(int i=1; i<=tot; i++){
		if(::res[i]==n){
			res.push_back(i);
		}
	}
	cout << res.size() << endl;
	for(int i=0; i<res.size(); i++) cout << res[i] << " ";
	return 0;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<res.size(); i++) cout << res[i] << " ";
               ~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1528 KB Output is correct
2 Correct 15 ms 1704 KB Output is correct
3 Correct 6 ms 1764 KB Output is correct
4 Correct 8 ms 1764 KB Output is correct
5 Correct 42 ms 1816 KB Output is correct
6 Correct 29 ms 1816 KB Output is correct
7 Correct 15 ms 1928 KB Output is correct
8 Correct 46 ms 1932 KB Output is correct
9 Correct 34 ms 1932 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1528 KB Output is correct
2 Correct 15 ms 1704 KB Output is correct
3 Correct 6 ms 1764 KB Output is correct
4 Correct 8 ms 1764 KB Output is correct
5 Correct 42 ms 1816 KB Output is correct
6 Correct 29 ms 1816 KB Output is correct
7 Correct 15 ms 1928 KB Output is correct
8 Correct 46 ms 1932 KB Output is correct
9 Correct 34 ms 1932 KB Output is correct
10 Correct 246 ms 1984 KB Output is correct
11 Correct 248 ms 1984 KB Output is correct
12 Correct 243 ms 1996 KB Output is correct
13 Correct 181 ms 1996 KB Output is correct
14 Correct 206 ms 1996 KB Output is correct
15 Correct 211 ms 2000 KB Output is correct
16 Correct 231 ms 2000 KB Output is correct
17 Correct 85 ms 2012 KB Output is correct
18 Correct 153 ms 2064 KB Output is correct
19 Correct 175 ms 2064 KB Output is correct
20 Correct 274 ms 2072 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1528 KB Output is correct
2 Correct 15 ms 1704 KB Output is correct
3 Correct 6 ms 1764 KB Output is correct
4 Correct 8 ms 1764 KB Output is correct
5 Correct 42 ms 1816 KB Output is correct
6 Correct 29 ms 1816 KB Output is correct
7 Correct 15 ms 1928 KB Output is correct
8 Correct 46 ms 1932 KB Output is correct
9 Correct 34 ms 1932 KB Output is correct
10 Correct 246 ms 1984 KB Output is correct
11 Correct 248 ms 1984 KB Output is correct
12 Correct 243 ms 1996 KB Output is correct
13 Correct 181 ms 1996 KB Output is correct
14 Correct 206 ms 1996 KB Output is correct
15 Correct 211 ms 2000 KB Output is correct
16 Correct 231 ms 2000 KB Output is correct
17 Correct 85 ms 2012 KB Output is correct
18 Correct 153 ms 2064 KB Output is correct
19 Correct 175 ms 2064 KB Output is correct
20 Correct 274 ms 2072 KB Output is correct
21 Correct 993 ms 2072 KB Output is correct
22 Execution timed out 1066 ms 2072 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1528 KB Output is correct
2 Correct 15 ms 1704 KB Output is correct
3 Correct 6 ms 1764 KB Output is correct
4 Correct 8 ms 1764 KB Output is correct
5 Correct 42 ms 1816 KB Output is correct
6 Correct 29 ms 1816 KB Output is correct
7 Correct 15 ms 1928 KB Output is correct
8 Correct 46 ms 1932 KB Output is correct
9 Correct 34 ms 1932 KB Output is correct
10 Correct 246 ms 1984 KB Output is correct
11 Correct 248 ms 1984 KB Output is correct
12 Correct 243 ms 1996 KB Output is correct
13 Correct 181 ms 1996 KB Output is correct
14 Correct 206 ms 1996 KB Output is correct
15 Correct 211 ms 2000 KB Output is correct
16 Correct 231 ms 2000 KB Output is correct
17 Correct 85 ms 2012 KB Output is correct
18 Correct 153 ms 2064 KB Output is correct
19 Correct 175 ms 2064 KB Output is correct
20 Correct 274 ms 2072 KB Output is correct
21 Correct 993 ms 2072 KB Output is correct
22 Execution timed out 1066 ms 2072 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1528 KB Output is correct
2 Correct 15 ms 1704 KB Output is correct
3 Correct 6 ms 1764 KB Output is correct
4 Correct 8 ms 1764 KB Output is correct
5 Correct 42 ms 1816 KB Output is correct
6 Correct 29 ms 1816 KB Output is correct
7 Correct 15 ms 1928 KB Output is correct
8 Correct 46 ms 1932 KB Output is correct
9 Correct 34 ms 1932 KB Output is correct
10 Correct 246 ms 1984 KB Output is correct
11 Correct 248 ms 1984 KB Output is correct
12 Correct 243 ms 1996 KB Output is correct
13 Correct 181 ms 1996 KB Output is correct
14 Correct 206 ms 1996 KB Output is correct
15 Correct 211 ms 2000 KB Output is correct
16 Correct 231 ms 2000 KB Output is correct
17 Correct 85 ms 2012 KB Output is correct
18 Correct 153 ms 2064 KB Output is correct
19 Correct 175 ms 2064 KB Output is correct
20 Correct 274 ms 2072 KB Output is correct
21 Correct 993 ms 2072 KB Output is correct
22 Execution timed out 1066 ms 2072 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1528 KB Output is correct
2 Correct 15 ms 1704 KB Output is correct
3 Correct 6 ms 1764 KB Output is correct
4 Correct 8 ms 1764 KB Output is correct
5 Correct 42 ms 1816 KB Output is correct
6 Correct 29 ms 1816 KB Output is correct
7 Correct 15 ms 1928 KB Output is correct
8 Correct 46 ms 1932 KB Output is correct
9 Correct 34 ms 1932 KB Output is correct
10 Correct 246 ms 1984 KB Output is correct
11 Correct 248 ms 1984 KB Output is correct
12 Correct 243 ms 1996 KB Output is correct
13 Correct 181 ms 1996 KB Output is correct
14 Correct 206 ms 1996 KB Output is correct
15 Correct 211 ms 2000 KB Output is correct
16 Correct 231 ms 2000 KB Output is correct
17 Correct 85 ms 2012 KB Output is correct
18 Correct 153 ms 2064 KB Output is correct
19 Correct 175 ms 2064 KB Output is correct
20 Correct 274 ms 2072 KB Output is correct
21 Correct 993 ms 2072 KB Output is correct
22 Execution timed out 1066 ms 2072 KB Time limit exceeded
23 Halted 0 ms 0 KB -