Submission #735150

#TimeUsernameProblemLanguageResultExecution timeMemory
735150colossal_pepeBali Sculptures (APIO15_sculpture)C++17
21 / 100
2 ms340 KiB
#include <iostream>
#include <cstring>
using namespace std;

using ll = long long;

const int INF = 1e9;
const int N = 100;

int n, a, b, dp[N + 5][N + 5];
ll x[N + 5];

bool isSubmask(ll sup, ll sub) {
    return (sup | sub) == sup;
}

int brutus(int l, int r, ll c) {
    if (r == n) return (isSubmask(c, x[r] - x[l - 1]) ? 0 : INF);
    if (dp[l][r] != -1) return dp[l][r];
    int &ret = dp[l][r];
    ret = brutus(l, r + 1, c);
    if (isSubmask(c, x[r] - x[l - 1])) ret = min(ret, 1 + brutus(r + 1, r + 1, c));
    // cout << l << ' ' << r << ' ' << ret << endl;
    return ret;
}

bool ok(ll target) {
    memset(dp, -1, sizeof dp);
    return 1 + brutus(1, 1, target) <= b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> a >> b;
    if (n > 100) exit(0);
    x[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        x[i] += x[i - 1];
    }
    ll c = 0;
    for (int _ = 0; _ <= 40; _++) {
        if (ok(c)) break;
        ll bit;
        for (bit = 0; bit <= 40; bit++) {
            c += (1 << bit);
            if (ok(c)) break;
        }
        for (ll i = 0; i < bit; i++) {
            c -= (1 << i);
        }
    }
    cout << c << '\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...