Submission #1218856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218856		kunzaZa183	Bali Sculptures (APIO15_sculpture)	C++20	71 / 100	1097 ms	18432 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, a, b;
  cin >> n >> a >> b;

  vector<int> vi(n);
  for (auto &a : vi)
    cin >> a;

  vector<vector<ll>> vvi(n, vector<ll>(n));
  vector<array<ll, 3>> elist;
  for (int i = 0; i < n; i++) {
    vvi[i][i] = vi[i];
    elist.push_back({i, i + 1, vvi[i][i]});
    for (int j = i + 1; j < n; j++) {
      vvi[i][j] = vvi[i][j - 1] + vi[j];
      elist.push_back({i, j + 1, vvi[i][j]});
    }
  }

  ll ans = 0;
  const int logn = 50;

  for (int i = logn; i >= 0; i--) {
    vector<array<ll, 3>> cure;

    vector<vector<pair<int, ll>>> adj(n);
    vector<set<int>> dp(n + 1);

    for (auto a : elist)
      if ((a[2] & (1ll << i)) == 0)
        adj[a[0]].push_back({a[1], a[2]});

    dp[0].insert(0);
    for (int i = 0; i < n; i++)
      for (auto a : adj[i])
        for (auto b : dp[i])
          dp[a.first].insert(b + 1);

    auto it = dp.back().lower_bound(a);
    if (it == dp.back().end() || *it > b)
      ans += (1ll << i);
    else {
      elist.clear();
      for (int i = 0; i < n; i++)
        for (auto a : adj[i])
          elist.push_back({i, a.first, a.second});
    }
  }

  cout << ans << '\n';
}

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