Submission #173624

#	Time	Username	Problem	Language	Result	Execution time	Memory
173624		aleks5d	Bootfall (IZhO17_bootfall)	C++17	44 / 100	434 ms	4596 KiB

bootfall

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>

using ll = long long int;
using ull = unsigned long long int;
using dd = double;
using ldd = long double;

namespace HASH {
  const ll mod197 = 1e9 + 7;
  const ll mod199 = 1e9 + 9;
  const ll modfft = 998244353;
  ll mod = mod199;
  void Hplus(ll& h, ll b) {
    h += b;
    if (h > mod)
      h -= mod;
  }

  void Hminus(ll& h, ll b) {
    h -= b;
    if (h < 0)
      h += mod;
  }

  void Hmuliply(ll& h, ll b) {
    h *= b;
    h %= mod;
  }

  ll Hdivider(ll x) {
    if (x < 0)
      x += mod;
    ll ans = 1;
    ll n = mod - 2;
    while (n) {
      if (n & 1)
        Hmuliply(ans, x);
      n >>= 1;
      Hmuliply(x, x);
    }
    return ans;
  }
}

namespace someUsefull {
  template<typename T1, typename T2>
    inline void checkMin(T1& a, T2 b) {
        if (a > b)
            a = b;
    }

    template<typename T1, typename T2>
    inline void checkMax(T1& a, T2 b) {
        if (a < b)
            a = b;
    }
    }

    //name spaces
    using namespace std;
using namespace HASH;
using namespace someUsefull;
//end of name spaces

//defines
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()

#define NO cout << "NO" << '\n';
#define YES cout << "YES" << '\n';
//end of defines

//debug defines
#ifdef HOME
#define debug(x) cout << #x << " " << x << endl;
#define debug_p(x) cout << #x << " " << x.ff << " " << x.ss << endl;
#define debug_v(x) {cout << #x << " "; for (auto ioi : x) cout << ioi << " "; cout << endl;}
#define debug_vp(x) {cout << #x << " "; for (auto ioi : x) cout << '[' << ioi.ff << " " << ioi.ss << ']'; cout << endl;}
#define debug_v_v(x) {cout << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cout << ioi2 << " "; cout << '\n';} cout << "*/" << #x << endl;}
  int jjj;
#define wait() cin >> jjj;
#define PO cout << "POMELO" << endl;
#define OL cout << "OLIVA" << endl;
#define gen_clock(x) ll x = clock(); cout << "Clock " << #x << " created" << endl;
#define check_clock(x) cout << "Time spent in " << #x << ": " << clock() - x << endl; x = clock();
#define reset_clock(x) x = clock();
#define say(x) cout << x << endl;
#else
#define debug(x) 0;
#define debug_p(x) 0;
#define debug_v(x) 0;
#define debug_vp(x) 0;
#define debug_v_v(x) 0;
#define wait() 0;
#define PO 0;
#define OL 0;
#define gen_clock(x) 0;
#define check_clock(x) 0;
#define reset_clock(x) 0;
#define say(x) 0;
#endif // HOME
//end of debug defines

void solve() {
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i)
    cin >> arr[i];
  vector<ll> dp(3e5);
  vector<int> canbe(3e5, 0);
  dp[0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = dp.size() - 1; j >= arr[i]; --j) {
      Hplus(dp[j], dp[j - arr[i]]);
    }
  }
  int ma = 0;
  for (int j = dp.size() - 1; j > 0; --j)
    if (dp[j]) {
      ma = j;
      break;
    }
  if (ma & 1) {
    cout << 0;
    return;
  }
  if (dp[ma >> 1] == 0) {
    cout << 0;
    return;
  }
  for (int i = 0; i < n; ++i) {
    if (i != -1) {
      for (int j = arr[i]; j < dp.size(); ++j) {
        Hminus(dp[j], dp[j - arr[i]]);
      }
    }
    int ma = 0;
    for (int i = dp.size() - 1; i > 0; --i) {
      if (dp[i]) {
        ma = i;
        break;
      }
    }
    debug(i);
    //vector<int> opa(dp.begin(), dp.begin() + ma + 1);
    //debug_v(opa);
    debug(ma);
    for (int i = 0; i * 2 <= ma; ++i) {
      if (dp[i]) {
        debug(i);
        debug(ma - i - i);
        ++canbe[ma - i - i];
      }
    }
    if (i != -1) {
      for (int j = dp.size() - 1; j >= arr[i]; --j) {
        Hplus(dp[j], dp[j - arr[i]]);
      }
    }
  }
  vector<int> ans;
  for (int i = 0; i < dp.size(); ++i) {
    if (canbe[i] == n) {
      ans.push_back(i);
    }
  }
  cout << ans.size() << '\n';
  for (int i : ans)
    cout << i << " ";

}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  t = 1;
  // cin >> t;
  for (int i = 0; i < t; ++i) {
    solve();
    cout << '\n';
  }
  return 0;

}

/*
    5
    3 2
    3 -2
    -2 -2
    -2 2
    0 0
    */

Compilation message (stderr)

bootfall.cpp: In function 'void solve()':
bootfall.cpp:137:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = arr[i]; j < dp.size(); ++j) {
                            ~~^~~~~~~~~~~
bootfall.cpp:92:19: warning: statement has no effect [-Wunused-value]
 #define debug(x) 0;
                   ^
bootfall.cpp:148:5: note: in expansion of macro 'debug'
     debug(i);
     ^~~~~
bootfall.cpp:92:19: warning: statement has no effect [-Wunused-value]
 #define debug(x) 0;
                   ^
bootfall.cpp:151:5: note: in expansion of macro 'debug'
     debug(ma);
     ^~~~~
bootfall.cpp:92:19: warning: statement has no effect [-Wunused-value]
 #define debug(x) 0;
                   ^
bootfall.cpp:154:9: note: in expansion of macro 'debug'
         debug(i);
         ^~~~~
bootfall.cpp:92:19: warning: statement has no effect [-Wunused-value]
 #define debug(x) 0;
                   ^
bootfall.cpp:155:9: note: in expansion of macro 'debug'
         debug(ma - i - i);
         ^~~~~
bootfall.cpp:166:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < dp.size(); ++i) {
                   ~~^~~~~~~~~~~

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