제출 #1305043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305043		LIA	Bootfall (IZhO17_bootfall)	C++17	100 / 100	626 ms	8036 KiB

bootfall

//
// Created by liasa on 23/11/2025.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (int i = s; i < e; ++i)
#define pll pair<ll, ll>

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  ll n;
  ll sum1 = 0;
  cin >> n;
  v<ll> a(n);

  ll mx = 0;
  lp(i, 0, n) {
    cin >> a[i];
    sum1 += a[i];
    mx = max(mx, a[i]);
  }
  mx *= n;
  mx += 2;

  v<ll> dp(mx);

  dp[0] = 1;
  const ll mod = 1e9 + 7;
  for (auto it : a) {
    for (ll sum = mx - 1; sum >= it; --sum) {
      dp[sum] += dp[sum - it];
      dp[sum] %= mod;
    }
  }
  if (sum1 % 2 != 0 || dp[sum1 / 2] == 0) {
    cout << 0 << endl;
    return 0;
  }

  v<ll> pos(mx + 1);
  v<ll> last(mx, -1); 
  lp(i, 0, n) {
    ll it = a[i];
    ll sumi = sum1 - a[i];
    for (ll sum = it; sum < mx; ++sum) {
      dp[sum] -= dp[sum - it];
      dp[sum] = (dp[sum] + mod) % mod;
    }
    for (ll j = 0; j <= sumi; ++j) {
      if (dp[j] > 0) {
        ll sum2 = abs(sumi - 2 * j);
        if (sum2 > 0 && last[sum2] != i) {
          pos[sum2]++;
          last[sum2] = i;
        }
      }
    }

    for (ll sum = mx - 1; sum >= it; --sum) {
      dp[sum] += dp[sum - it];
      dp[sum] = (dp[sum] + mod) % mod;
    }
  }

  v<ll> answ;
  for (ll k = 1; k < mx; ++k) {
    if (pos[k] == n)
      answ.push_back(k);
  }
  cout << answ.size() << endl;
  for (auto it : answ)
    cout << it << " ";
}

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