제출 #1218848

#제출 시각아이디문제언어결과실행 시간메모리
1218848kunzaZa183Bali Sculptures (APIO15_sculpture)C++20
50 / 100
499 ms120440 KiB
#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<ll> dp(n + 1, n + 3);

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

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

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

  cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...