제출 #1321530

#제출 시각아이디문제언어결과실행 시간메모리
1321530AMel0nBali Sculptures (APIO15_sculpture)C++20
100 / 100
63 ms472 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll N, A, B;
vector<ll> V;
vector<ll> PS;
ll sum(ll a, ll b) {
    return PS[b+1] - PS[a];
}

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> A >> B;
    V.resize(N), PS.resize(N+1);
    ll UB = 0;
    for(ll i = 0; i < N; i++) {
        cin >> V[i];
        PS[i+1] = PS[i] + V[i];
        UB += V[i];
    }
    if (A == 1) {
        UB = __lg(UB);
        ll cur = (1ll << UB+1ll) - 1ll;
        for(ll k = UB; k >= 0; k--) {
            cur ^= (1ll << k);
            vector<ll> dp(N+1, INF); // dp[i] = min # of partitions
            dp[0] = 0;
            for(ll i = 0; i <= N; i++) {
                for(ll j = 0; j < i; j++) {
                    if ((cur | sum(j, i-1)) == cur) {
                        dp[i] = min(dp[i], 1 + dp[j]);
                    }
                }
            }
            if (dp[N] > B) cur ^= (1ll << k);
        }
        cout << cur << endl;
    } else {
        UB = __lg(UB);
        ll cur = (1ll << UB+1ll) - 1ll;
        for(ll k = UB; k >= 0; k--) {
            cur ^= (1ll << k);
            vector<vector<bool>> dp(N+1, vector<bool>(B+1)); // dp[i][# of partitions]
            dp[0][0] = true;
            for(ll i = 0; i <= N; i++) {
                for(ll j = 0; j < i; j++) {
                    for(ll k = 1; k <= B; k++) {
                        dp[i][k] = dp[i][k] | (dp[j][k-1] & ((cur | sum(j, i-1)) == cur));
                    }
                }
            }
            bool yes = false;
            for(ll k = A; k <= B; k++) {
                if (dp[N][k]) yes = true;
            }
            if (!yes) cur ^= (1ll << k);
        }
        cout << cur << endl;
    }
}
#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...