제출 #1153812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153812		Gabituss	Bootfall (IZhO17_bootfall)	C++20	0 / 100	1095 ms	584 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

//@formatter:off
using ll = long long;
using ld = double;
template<typename T> istream &operator>>(istream &is, vector<T> &a);
template<typename T> ostream &operator<<(ostream &os, vector<T> &a);
//@formatter:on
#define int long long
const int Vmax = 10000;
const int mod1 = 1e9 + 37;
const int mod2 = 1e9 + 7;
const int N = 10000 + Vmax + 50;

int add(int a, int b, int mod) {
      if (a + b >= mod) return a + b - mod;
      return a + b;
}

int sub(int a, int b, int mod) {
      if (a - b < 0) return a - b + mod;
      return a - b;
}

signed main() {
#ifdef LOCAL
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
#else
      ios_base::sync_with_stdio(false);
      cin.tie(0);
#endif

      int n;
      cin >> n;

      vector<int> a(n);
      cin >> a;

      vector<int> ans;
      for (int V = 1; V <= Vmax; ++V) {
            vector<int> b = a;
            b.push_back(V);
            vector<int> dp1(N);
            vector<int> dp2(N);
            dp1[0] = 1;
            dp2[0] = 1;
            ll sum = std::accumulate(b.begin(), b.end(), 0ll);
            for (int i = 0; i <= n; ++i) {
                  for (int j = N - 1; j >= b[i]; --j) {
                        if (j - b[i] >= 0) {
                              dp1[j] = add(dp1[j - b[i]], dp1[j], mod1);
                              dp2[j] = add(dp2[j - b[i]], dp2[j], mod2);
                        }
                  }
            }

            bool good = true;
            for (int i = 0; i <= n; ++i) {
                  if ((sum - b[i]) % 2 == 1) {
                        good = false;
                        continue;
                  }
                  for (int j = b[i]; j < N; ++j) {
                        if (j - b[i] >= 0) {
                              dp1[j] = sub(dp1[j], dp1[j - b[i]], mod1);
                              dp2[j] = sub(dp2[j], dp2[j - b[i]], mod2);
                        }
                  }
                  good &= (dp1[(sum - b[i]) / 2] != 0 | dp2[(sum - b[i]) / 2] != 0);
                  for (int j = N - 1; j >= b[i]; --j) {
                        if (j - b[i] >= 0) {
                              dp1[j] = add(dp1[j - b[i]], dp1[j], mod1);
                              dp2[j] = add(dp2[j - b[i]], dp2[j], mod2);
                        }
                  }
            }
            if (good) {
                  ans.push_back(V);
            }
      }
      cout << ans.size() << "\n";
      cout << ans;
}

// region POZOR
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
      for (int i = 0; i < a.size(); i++)
            os << a[i] << " \n"[i == a.size() - 1];
      return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
      for (auto &i: a)
            is >> i;
      return is;
}
// endregion

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