oj.uz

Submission #333621

# Submission time Handle Problem Language Result Execution time Memory
333621 2020-12-07T08:53:24 Z tengiz05 Bootfall (IZhO17_bootfall) C++17
0 / 100
 1000 ms 1644 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 105;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N], n, m, k, rev[N];
bool dp[N*N][N];
bool sp[N*N][N];
bool calc(int x){
	int i, j;
	memset(dp, 0, sizeof(dp));
	bool pos = true;
	for(k=0;k<=n;k++){
		memset(dp, 0, sizeof(dp));
		swap(a[k], x);
		dp[0][0] = 1;
		int sum = 0;
		for(i=1;i<=n;i++)sum += a[i];
		for(i=1;i<=sum;i++){
			for(j=1;j<=n;j++){
				dp[i][j] = dp[i][j-1];
				if(i-a[j] >= 0)dp[i][j] |= dp[i-a[j]][j-1];
			}
		}
		if(!dp[sum/2][n] || sum%2!=0)pos = false;
		swap(a[k], x);
	}
	return pos;
}
void solve(int test_case){
	int i, j;
	cin >> n;
	int sum = 0;
	for(i=1;i<=n;i++){
		cin >> a[i];
		sum += a[i];
	}
	vector<int> ans;
	for(i=1;i<=sum;i++){
		if(calc(i))ans.pb(i);
	}
	cout << ans.size() << '\n';
	for(auto x : ans)cout << x << ' ';
	cout << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

bootfall.cpp: In function 'void solve(long long int)':
bootfall.cpp:39:9: warning: unused variable 'j' [-Wunused-variable]
   39 |  int i, j;
      |         ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1516 KB Output is correct
2 Correct 17 ms 1516 KB Output is correct
3 Correct 2 ms 1408 KB Output is correct
4 Correct 228 ms 1644 KB Output is correct
5 Execution timed out 1004 ms 1560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1516 KB Output is correct
2 Correct 17 ms 1516 KB Output is correct
3 Correct 2 ms 1408 KB Output is correct
4 Correct 228 ms 1644 KB Output is correct
5 Execution timed out 1004 ms 1560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1516 KB Output is correct
2 Correct 17 ms 1516 KB Output is correct
3 Correct 2 ms 1408 KB Output is correct
4 Correct 228 ms 1644 KB Output is correct
5 Execution timed out 1004 ms 1560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1516 KB Output is correct
2 Correct 17 ms 1516 KB Output is correct
3 Correct 2 ms 1408 KB Output is correct
4 Correct 228 ms 1644 KB Output is correct
5 Execution timed out 1004 ms 1560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1516 KB Output is correct
2 Correct 17 ms 1516 KB Output is correct
3 Correct 2 ms 1408 KB Output is correct
4 Correct 228 ms 1644 KB Output is correct
5 Execution timed out 1004 ms 1560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1516 KB Output is correct
2 Correct 17 ms 1516 KB Output is correct
3 Correct 2 ms 1408 KB Output is correct
4 Correct 228 ms 1644 KB Output is correct
5 Execution timed out 1004 ms 1560 KB Time limit exceeded
6 Halted 0 ms 0 KB -