Submission #236477

#	Time	Username	Problem	Language	Result	Execution time	Memory
236477		maskoff	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1103 ms	109176 KiB

bootfall

#include <bits/stdc++.h>
#include <ext/rope>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair
 
#define pss pair<line*, line*>
 
using namespace std;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
                                 
const ll inf = 1e18;
const int MOD = 1e9 + 7;
 
const int dx[] = {-1, +1, -2, +2, -2, +2, -1, +1};
const int dy[] = {-2, -2, -1, -1, +1, +1, +2, +2};
 
int const N = 5e3 + 5;
int const M = 2e6;

int main() {                 
#ifdef Mask                                                         
  freopen(".in", 	"r", stdin);
  freopen(".out", "w", stdout);  
#endif
	ios_base :: sync_with_stdio(false);               
  cin.tie(nullptr);
  int n;
  cin >> n;
  int sum = 0;
  int a[n + 1];
  for (int i = 1; i <= n; i++)
  	cin >> a[i], sum += a[i];
  int d[n + 1][sum + 100001];
  for (int i = 1; i <= n; i++)
  	for (int j = 0; j <= sum + 100000; j++)
  		d[i][j] = 0;

  for (int del = 0; del <= n; del++) {
  	int dp[n + 1][sum + 1];
  	
  	for (int i = 0; i <= n; i++)
  		for (int w = 0; w <= sum; w++)
  			dp[i][w] = 0;

  	dp[0][0] = 1;
   	
   	for (int i = 0; i < n; i++) {
   	 	for (int w = 0; w <= sum; w++) 
   	 		dp[i + 1][w] |= dp[i][w];

   	 	if (i + 1 == del)
   	 		continue;

   	 	for (int w = 0; w <= sum; w++) 
   	 		if (a[i + 1] + w <= sum)
   	 			dp[i + 1][w + a[i + 1]] |= dp[i][w];
   	}
   	for (int w = 0; w <= sum; w++)
   		if (dp[n][w] == 1)
   			d[del][w] = 1;	
  }

  vector<int> ans;
  for (int k = 1; k <= 50000; k++)  {
  	int ok = true;
  	for (int del = 0; del <= n; del++) {
  		int all = sum + k;
  		if (del == 0) all -= k;
  		else all -= a[del];
  		if (all % 2 == 1) {
  			ok = false;
  			break;
  		}
  		int need = all / 2;
  		if (d[del][need] == 0) {
  			ok = false;
  			break;
  		}
  	}
  	if (ok == true)
  		ans.pb(k);
  }
 	cout << ans.size() << endl;
 	for (int to : ans)
 		cout << to << " ";      
	return 0;
 
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35