Submission #514691

#	Time	Username	Problem	Language	Result	Execution time	Memory
514691		Mazaalai	Bootfall (IZhO17_bootfall)	C++17	100 / 100	710 ms	5380 KiB

bootfall

#include <bits/stdc++.h>
#define pb push_back
#define LINE "-------------------\n"
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
const int N = 500+1;
const int M = 500*500+1;
vector <int> ans;
int n, m, nums[N];
const ll MOD = 1e9+7;
ll dp[M], dp1[M], sum;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> nums[i];
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		int& x = nums[i];
		sum += x;
		for (int j = M-1; j >= x; j--) 
			dp[j] = (dp[j] + dp[j-x]) % MOD;
	}
	if (sum & 1 || dp[sum / 2] == 0) {
		cout << "0\n";
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		int& x = nums[i];
		for (int j = x; j <= M-1; j++) 
			dp[j] = (dp[j] - dp[j-x] + MOD) % MOD;
		
		for (int j = M-1; j >= 0; j--) 
			if (dp[j] > 0 && 2 * j + x - sum >= 0) dp1[2 * j + x - sum]++;
			
		for (int j = M-1; j >= x; j--) 
			dp[j] = (dp[j] + dp[j-x]) % MOD;
	}
	for (int j = 0; j < M; j++) {
		if (dp1[j] == n) ans.pb(j);
	}
	cout << sz(ans) << '\n';
	for (auto&el:ans) cout << el << ' '; cout << '\n';
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:47:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   47 |  for (auto&el:ans) cout << el << ' '; cout << '\n';
      |  ^~~
bootfall.cpp:47:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   47 |  for (auto&el:ans) cout << el << ' '; cout << '\n';
      |                                       ^~~~

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