Submission #514689

#	Time	Username	Problem	Language	Result	Execution time	Memory
514689		Mazaalai	Bootfall (IZhO17_bootfall)	C++17	0 / 100	21 ms	3000 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() {

    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;
	}
	// for (int i = 1; i <= 10; i++) cout << dp[i] << " \n"[i==10];
	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;
		/* 
			left = (sum - x + a) / 2 == j;
			sum-x+a = 2j
			a = 2j+x-sum;
		*/
		// cout << LINE;B
		// cout << x << ":\n";
		// cout << "dp: ";
		// for (int i = 1; i <= 10; i++) cout << dp[i] << " \n"[i==10];
		for (int j = M-1; j >= 0; j--) {
			int a = 2 * j + x - sum;
			if (dp[j] > 0 && a >= 0) {
				// cout << j << " " << a << '\n';
				dp1[a]++;
				// cout << 2 * j + x - sum << ' ';
			}
		}
		
		// cout << "\n";
		for (int j = M-1; j >= x; j--) 
			dp[j] = (dp[j] + dp[j-x]) % MOD;

		// cout << "dp: ";
		// for (int i = 1; i <= 10; i++) cout << dp[i] << " \n"[i==10];
	}
	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:64:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   64 |  for (auto&el:ans) cout << el << ' '; cout << '\n';
      |  ^~~
bootfall.cpp:64:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   64 |  for (auto&el:ans) cout << el << ' '; cout << '\n';
      |                                       ^~~~
bootfall.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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