Submission #1192277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192277		lucaskojima	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	369 ms	472 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;

template<typename T>
void chmin(T &a, T b) { if (b < a) a = b; }

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<int> dp(n, INF);
    if (ok(y[0])) dp[0] = 1;

    for (int i = 1; i < n; i++) {
      if (ok(p[i]))
        dp[i] = 1;
      for (int j = 0; j < i; j++)
        if (ok(p[i] - p[j]))
          chmin(dp[i], dp[j] + 1);
    }

    if (dp[n - 1] > b)
      ans += (1LL << bit);
  }

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

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