Submission #1192275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192275		lucaskojima	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	1095 ms	692 KiB

sculpture

#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n, a, b; cin >> n >> a >> b;
  vector<int> y(n); for (auto &x : y) cin >> x;

  vector<ll> p(n); p[0] = y[0];
  for (int i = 1; i < n; i++)
    p[i] = p[i - 1] + y[i];

  ll ans = 0;
  for (int bit = 40; bit >= 0; bit--) {
    auto ok = [&](ll sum) -> bool {
      if (sum & (1LL << bit)) return false;
      for (int i = 40; i > bit; i--)
        if (!(ans & (1LL << i)) && (sum & (1LL << i)))
          return false;
      return true;
    };

    vector dp(n, vector<int>(b + 1));
    for (int i = 0; i < n; i++)
      dp[i][1] = ok(p[i]);

    for (int i = 1; i < n; i++)
      for (int k = 1; k <= b; k++)
        for (int j = 0; j < i; j++)
          if (ok(p[i] - p[j]))
            dp[i][k] |= dp[j][k - 1];

    bool f = true;
    for (int k = a; k <= b; k++)
      if (dp[n - 1][k] == true)
        f = false;

    if (f)
      ans += (1LL << bit);
  }

  cout << ans << nl;
  return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 0 / 29