Submission #199928

#	Time	Username	Problem	Language	Result	Execution time	Memory
199928		quocnguyen1012	Bootfall (IZhO17_bootfall)	C++14	100 / 100	553 ms	3448 KiB

bootfall

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 505, mod = 1e9 + 7;

int N, a[maxn];
int f[maxn * maxn];
vector<int> ret;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N;
  int sum = 0;
  f[0] = 1;
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    sum += a[i];
    for (int j = sum; j >= a[i]; --j){
      f[j] += f[j - a[i]];
      f[j] %= mod;
    }
  }
  if (sum & 1 || f[sum / 2] == 0){
    cout << "0";
    return 0;
  }
  for (int i = 1; i < maxn * maxn; ++i){
    ret.pb(i);
  }
  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;
    }
    vector<int> vi;
    for (auto & all : ret){
      int val = sum - a[i] + all;
      if (val < 0 || val % 2 == 1 || f[val / 2] == 0){
        continue;
      }
      vi.pb(all);
    }
    swap(vi, ret);
    for (int j = sum; j >= a[i]; --j){
      f[j] += f[j - a[i]];
      f[j] %= mod;
    }
  }
  cout << ret.size() << '\n';
  for (auto & it : ret) cout << it << ' ' ;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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