Submission #166745

#TimeUsernameProblemLanguageResultExecution timeMemory
166745abilBootfall (IZhO17_bootfall)C++14
100 / 100
553 ms2076 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pb push_back #define mk make_pair #define all(s) s.begin(),s.end() //#define int long long using namespace std; const int N = (1e6 + 12); const int mod = (1e9 + 7); const int INF = (0x3f3f3f3f); int a[N], f[N]; set<int > s; bitset< N > b; main() { int n, sum = 0; scanf("%d", &n); for(int i = 1;i <= n; i++){ scanf("%d", &a[i]); } f[0] = 1; for(int i = 1;i <= n; i++){ for(int j = sum + a[i];j >= a[i]; j--){ f[j] += f[j - a[i]]; if(f[j] >= mod){ f[j] -= mod; } } sum += a[i]; } if(!f[sum / 2] || sum & 1){ cout << 0; return 0; } for(int i = 1;i <= sum; i++){ b[i] = 1; } for(int i = 1;i <= n; i++){ for(int j = a[i];j <= sum; j++){ f[j] -= f[j - a[i]]; if(f[j] < 0){ f[j] += mod; } } for(int j = 1;j <= sum; j++){ if((sum - a[i] + j) & 1 || !f[(sum - a[i] + j) / 2]){ b[j] = 0; } } for(int j = sum;j >= a[i]; j--){ f[j] += f[j - a[i]]; if(f[j] >= mod){ f[j] -= mod; } } } cout << b.count() << endl; for(int i = 1;i <= sum; i++){ if(b[i]){ cout << i << " "; } } }

Compilation message (stderr)

bootfall.cpp:19:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bootfall.cpp:24:8: 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...