Submission #36837

#TimeUsernameProblemLanguageResultExecution timeMemory
36837szawinisBootfall (IZhO17_bootfall)C++14
100 / 100
709 ms7752 KiB
#include <bits/stdc++.h> using namespace std; const int N = 501, M = 500*500+1; int n, sum, a[N], cnt[M]; long long dp[M], tmp[M]; int main() { scanf("%d", &n); dp[0] = 1; for(int i = 0; i < n; i++) { scanf("%d", a+i); sum += a[i]; for(int j = M-1; j >= a[i]; j--) dp[j] += dp[j - a[i]]; } if(sum % 2 || !dp[sum >> 1]) printf("0"), exit(0); for(int i = 0; i < n; i++) { copy(dp, dp+M, tmp); for(int j = a[i]; j < M; j++) tmp[j] -= tmp[j - a[i]]; // pay attention to order, only want to remove ones invalidated, not all combinations for(int x = 0; x < M; x++) { int val = sum - a[i] + x; // new sum of entire sequence including n+1 cnt[x] += val % 2 == 0 && tmp[val >> 1]; } } vector<int> ans; for(int x = 0; x < M; x++) if(cnt[x] == n) ans.push_back(x); printf("%d\n", ans.size()); for(int x: ans) printf("%d ", x); }

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:26:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                           ^
bootfall.cpp:8:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bootfall.cpp:11:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...