Submission #41494

#	Time	Username	Problem	Language	Result	Execution time	Memory
41494		krauch	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	168 ms	1132 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define y1 kekek
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

const ll ool = 1e18 + 9;
const int N = 2e3 + 6, oo = 1e9 + 9, base = 1e9 + 7;

int n, A, B, a[N], d[N][N], d2[N];
ll ans = ool;
bool bit[22];

bool check(ll mask1, ll mask2, int pos) {
    mask1 >>= 1ll * pos;
    mask2 >>= 1ll * pos;
    return ((mask1 | mask2) == mask1);
}

bool calc(ll mask, int pos) {
    d[0][0] = 1;
    forn(i, 1, n) {
        forn(j, 1, B) {
            d[i][j] = 0;
            ll sum = 0;
            for1(k, i, 1) {
                sum += a[k];
                if (!check(mask, sum, pos)) continue;
                d[i][j] |= d[k - 1][j - 1];
            }
        }
    }
    forn(i, A, B) {
        if (d[n][i]) return 1;
    }
    return 0;
}

bool calc2(ll mask, int pos) {
    d2[0] = 0;
    forn(i, 1, n) {
        d2[i] = oo;
        ll sum = 0;
        for1(k, i, 1) {
            sum += a[k];
            if (!check(mask, sum, pos)) continue;
            d2[i] = min(d2[i], d2[k - 1] + 1);
        }
    }
    return (d2[n] <= B);
}

int main() {
    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #endif

    cin >> n >> A >> B;
    forn(i, 1, n) {
        cin >> a[i];
    }

    ll ans = 0;
    for1(i, 41, 0) {
        ans |= (1ll << i);
        bool res = (A == 1 ? calc2(ans, i) : calc(ans, i));
        ans ^= (1ll << i);
        if (!res) ans |= (1ll << (i + 1));
    }
    bool res = (A == 1 ? calc2(ans, 0) : calc(ans, 0));
    if (!res) ans++;

    cout << ans << "\n";

    return 0;
}

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