Submission #36836

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
36836	2017-12-16 04:35:10	szawinis	Bootfall (IZhO17_bootfall)	C++14	100 / 100	836 ms	8728 KiB

bootfall

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int N = 501, M = 3e5+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);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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);
                   ^

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