Submission #337573

#	Time	Username	Problem	Language	Result	Execution time	Memory
337573		boykut	Bootfall (IZhO17_bootfall)	C++14	100 / 100	406 ms	3692 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500 * 500 + 1;
int dp[MAXN], used[MAXN], a[500], sum;

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   
   int n;
   cin >> n;
   
   dp[0] = 1;
   for (int i = 0; i < n; i++) {
      cin >> a[i];
      for (int x = sum; x >= 0; x--) {
         dp[x + a[i]] += dp[x];
      }
      sum += a[i];
   }
   
   if (sum % 2 == 1 || dp[sum / 2] == 0) {
      cout << "0\n";
   } else {
      fill (used, used + MAXN, 1);
      
      for (int i = 0; i < n; i++) {
         sum -= a[i];
         for (int x = 0; x <= sum; x++) {
            dp[x + a[i]] -= dp[x];
         }
         
         for (int half = 1; half < MAXN; half++) {
            if ((sum + half) % 2 == 1 || dp[(sum + half) / 2] == 0)
               used[half] = 0;
         }
         
         for (int x = sum; x >= 0; x--) {
            dp[x + a[i]] += dp[x];
         }
         sum += a[i];
      }
      
      vector <int> ans;
      
      for (int half = 1; half < MAXN; half++) {
         if (used[half])
            ans.push_back(half);
      }
      
      cout << ans.size() << '\n';
      for (int i = 0; i < ans.size(); i++)
         cout << ans[i] << ' ';
      cout << '\n';
   }
   return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:54:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |       for (int i = 0; i < ans.size(); 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