Submission #386230

#	Time	Username	Problem	Language	Result	Execution time	Memory
386230		patrikpavic2	Bootfall (IZhO17_bootfall)	C++17	100 / 100	264 ms	35220 KiB

bootfall

#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <vector>
#include <algorithm>

#define PB push_back

using namespace std;

const int N = 505;
const int OFF = N * N;

bitset < 2 * OFF > dp[N];
bitset < 2 * OFF > pres; 

int n, sz = 1, A[N], mogu = 0;

void solve(int l, int r){
	if(l > r) return;
	if(l == r){
		pres = pres & dp[sz - 1];
		if(!l){
			dp[sz] = (dp[sz - 1] << A[0]) | (dp[sz - 1] >> A[0]);
			mogu = dp[sz][OFF];
		}
		return;
	}
	int mid = (l + r) / 2;
	if(mid + 1 <= r){
		for(int i = l;i <= mid;i++){
			dp[sz] = (dp[sz - 1] << A[i]) | (dp[sz - 1] >> A[i]);
			sz++;
		}
		solve(mid + 1, r);
		sz -= mid - l + 1;
	}
	if(l <= mid){
		for(int i = mid + 1;i <= r;i++){
			dp[sz] = (dp[sz - 1] << A[i]) | (dp[sz - 1] >> A[i]);
			sz++;
		}
		solve(l, mid);
		sz -= r - mid;		
	}
}

vector < int > sol;

int main(){
	dp[0][OFF] = 1;
	for(int i = 0;i < 2 * OFF;i++)
		pres[i] = 1;
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d", A + i);
	}
	solve(0, n - 1);
	if(!mogu){
		printf("0\n");
		return 0;
	}
	for(int i = 0;i < 2 * OFF;i++)
		if(pres[i]) sol.PB(abs(i - OFF));
	sort(sol.begin(), sol.end());
	sol.erase(unique(sol.begin(), sol.end()), sol.end());
	printf("%d\n", (int)sol.size());
	for(int x : sol)
		printf("%d ", x);
	printf("\n");
	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bootfall.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

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