oj.uz

Submission #500862

# Submission time Handle Problem Language Result Execution time Memory
500862 2022-01-01T13:33:27 Z EliteCallsYou Bootfall (IZhO17_bootfall) C++17
13 / 100
 1000 ms 16156 KB 
# include <bits/stdc++.h>
using namespace std ;
//############################################################################
# define read(a)/**/for(int i=0;i<int(sizeof(a)/sizeof(a[0]));i++){cin>>a[i];}
# define print(x)/**/for(auto zx:x){cout<<zx<<' ';}
const char* tochar(string a){return a.c_str();}
void files(){freopen("planting.in","r",stdin);freopen("planting.out","w",stdout);}
void speed(){ios_base::sync_with_stdio(false);cin.tie(0);}
long long gcd(long long a,long long b){if(!b){return a;}a%=b;return gcd(b,a);}
long long lcm(long long a,long long b){return a /gcd(a,b) * b;}
//###########################################################################
const int N = 3e5 + 5 ;
const long long MOD = 1e17+7 ;
//###########################################################################
void hack(){}
//###########################################################################
int main(){
	int n, sum = 0 ; cin >> n ;
	int ar[n+1] ;
	for ( int i = 1 ; i <= n ; i ++ ){
		cin >> ar[i] ;
		sum += ar[i] ;
	}
	if ( sum%2 ){
		cout << "0\n";
		return 0 ;
	}
	
	bool dp[n+1][250001] = {false} ;
	for ( int i = 0 ; i <= n ; i ++ ){
		dp[i][0] = true ;

		for ( int it = 1 ; it <= n ; it ++ ){
			if ( it == i ){continue;}
			for ( int j = 250001-ar[it] ; j > -1 ; j -- ){
				if ( dp[i][j] ){
					dp[i][j+ar[it]] = true ;
				}
			}
		}
	}


	if ( !dp[0][sum/2] ){
		cout << "0\n" ;
		return 0 ;
	}

	vector < int > ans ;
	for ( int cur = 1 ; cur <= sum ; cur ++ ){

		bool ok = true ;

		for ( int j = 1 ; j <= n ; j ++ ){
			int s = sum-ar[j]+cur ;
			if ( s%2 || s < 0 ){
				ok = false ;
				break ;
			}
			if ( !dp[j][s/2] ){
				ok = false ;
				break ;
			}
		}
		if ( ok ){
			ans.push_back(cur) ;
		}
	}


	cout << ans.size() << '\n' ;
	for ( auto it : ans ){
		cout << it << ' ' ;
	}
}

Compilation message

bootfall.cpp: In function 'void files()':
bootfall.cpp:7:21: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | void files(){freopen("planting.in","r",stdin);freopen("planting.out","w",stdout);}
      |              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:7:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | void files(){freopen("planting.in","r",stdin);freopen("planting.out","w",stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1436 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 3 ms 1184 KB Output is correct
4 Correct 5 ms 1440 KB Output is correct
5 Correct 37 ms 3404 KB Output is correct
6 Correct 22 ms 2380 KB Output is correct
7 Correct 10 ms 2000 KB Output is correct
8 Correct 39 ms 3360 KB Output is correct
9 Correct 33 ms 2892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1436 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 3 ms 1184 KB Output is correct
4 Correct 5 ms 1440 KB Output is correct
5 Correct 37 ms 3404 KB Output is correct
6 Correct 22 ms 2380 KB Output is correct
7 Correct 10 ms 2000 KB Output is correct
8 Correct 39 ms 3360 KB Output is correct
9 Correct 33 ms 2892 KB Output is correct
10 Correct 234 ms 7852 KB Output is correct
11 Correct 235 ms 7864 KB Output is correct
12 Correct 243 ms 7856 KB Output is correct
13 Correct 172 ms 6820 KB Output is correct
14 Correct 257 ms 7372 KB Output is correct
15 Correct 220 ms 7372 KB Output is correct
16 Correct 228 ms 7864 KB Output is correct
17 Correct 115 ms 4812 KB Output is correct
18 Correct 204 ms 6388 KB Output is correct
19 Correct 170 ms 6872 KB Output is correct
20 Correct 256 ms 7856 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1436 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 3 ms 1184 KB Output is correct
4 Correct 5 ms 1440 KB Output is correct
5 Correct 37 ms 3404 KB Output is correct
6 Correct 22 ms 2380 KB Output is correct
7 Correct 10 ms 2000 KB Output is correct
8 Correct 39 ms 3360 KB Output is correct
9 Correct 33 ms 2892 KB Output is correct
10 Correct 234 ms 7852 KB Output is correct
11 Correct 235 ms 7864 KB Output is correct
12 Correct 243 ms 7856 KB Output is correct
13 Correct 172 ms 6820 KB Output is correct
14 Correct 257 ms 7372 KB Output is correct
15 Correct 220 ms 7372 KB Output is correct
16 Correct 228 ms 7864 KB Output is correct
17 Correct 115 ms 4812 KB Output is correct
18 Correct 204 ms 6388 KB Output is correct
19 Correct 170 ms 6872 KB Output is correct
20 Correct 256 ms 7856 KB Output is correct
21 Execution timed out 1070 ms 16156 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1436 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 3 ms 1184 KB Output is correct
4 Correct 5 ms 1440 KB Output is correct
5 Correct 37 ms 3404 KB Output is correct
6 Correct 22 ms 2380 KB Output is correct
7 Correct 10 ms 2000 KB Output is correct
8 Correct 39 ms 3360 KB Output is correct
9 Correct 33 ms 2892 KB Output is correct
10 Correct 234 ms 7852 KB Output is correct
11 Correct 235 ms 7864 KB Output is correct
12 Correct 243 ms 7856 KB Output is correct
13 Correct 172 ms 6820 KB Output is correct
14 Correct 257 ms 7372 KB Output is correct
15 Correct 220 ms 7372 KB Output is correct
16 Correct 228 ms 7864 KB Output is correct
17 Correct 115 ms 4812 KB Output is correct
18 Correct 204 ms 6388 KB Output is correct
19 Correct 170 ms 6872 KB Output is correct
20 Correct 256 ms 7856 KB Output is correct
21 Execution timed out 1070 ms 16156 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1436 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 3 ms 1184 KB Output is correct
4 Correct 5 ms 1440 KB Output is correct
5 Correct 37 ms 3404 KB Output is correct
6 Correct 22 ms 2380 KB Output is correct
7 Correct 10 ms 2000 KB Output is correct
8 Correct 39 ms 3360 KB Output is correct
9 Correct 33 ms 2892 KB Output is correct
10 Correct 234 ms 7852 KB Output is correct
11 Correct 235 ms 7864 KB Output is correct
12 Correct 243 ms 7856 KB Output is correct
13 Correct 172 ms 6820 KB Output is correct
14 Correct 257 ms 7372 KB Output is correct
15 Correct 220 ms 7372 KB Output is correct
16 Correct 228 ms 7864 KB Output is correct
17 Correct 115 ms 4812 KB Output is correct
18 Correct 204 ms 6388 KB Output is correct
19 Correct 170 ms 6872 KB Output is correct
20 Correct 256 ms 7856 KB Output is correct
21 Execution timed out 1070 ms 16156 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1436 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 3 ms 1184 KB Output is correct
4 Correct 5 ms 1440 KB Output is correct
5 Correct 37 ms 3404 KB Output is correct
6 Correct 22 ms 2380 KB Output is correct
7 Correct 10 ms 2000 KB Output is correct
8 Correct 39 ms 3360 KB Output is correct
9 Correct 33 ms 2892 KB Output is correct
10 Correct 234 ms 7852 KB Output is correct
11 Correct 235 ms 7864 KB Output is correct
12 Correct 243 ms 7856 KB Output is correct
13 Correct 172 ms 6820 KB Output is correct
14 Correct 257 ms 7372 KB Output is correct
15 Correct 220 ms 7372 KB Output is correct
16 Correct 228 ms 7864 KB Output is correct
17 Correct 115 ms 4812 KB Output is correct
18 Correct 204 ms 6388 KB Output is correct
19 Correct 170 ms 6872 KB Output is correct
20 Correct 256 ms 7856 KB Output is correct
21 Execution timed out 1070 ms 16156 KB Time limit exceeded
22 Halted 0 ms 0 KB -