제출 #1357451

#제출 시각아이디문제언어결과실행 시간메모리
1357451Desh03Bali Sculptures (APIO15_sculpture)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>

using namespace std;

int n, a, b;
vector<int> p;
map<tuple<long long, int, int>, long long> dp;

long long go(long long Or, int i, int k) {
    if (i == n) return a <= k && k <= b ? 0 : -1;
    if (k >= b) return -1;
    if (dp.find({Or, i, k}) != dp.end()) return dp[{Or, i, k}];
    long long ans = -1, cur = 0;
    vector<pair<long long, int>> v;
    for (int j = i; j < n; j++) {
        cur += p[j];
        v.push_back({(~Or & cur), -j});
    }
    sort(v.begin(), v.end());
    int l = 0, r = v.size() - 1;
    while (l <= r) {
        int i = l + r >> 1;
        auto nxt = go(Or + v[i].first, -v[i].second + 1, k + 1);
        if (nxt != -1) {
            if (ans == -1) ans = v[i].first + nxt;
            else ans = min(ans, v[i].first + nxt);
            r = i - 1;
        } else {
            l = i + 1;
        }
    }
    return dp[{Or, i, k}] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    p.resize(n);
    for (int &x : p) {
        cin >> x;
    }
    cout << go(0, 0, 0) << '\n';
    return 0;
}
#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...