제출 #1359940

#제출 시각아이디문제언어결과실행 시간메모리
1359940kantaponzBali Sculptures (APIO15_sculpture)C++20
0 / 100
0 ms360 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int n, a, b;
ll y[2005];
ll qs[2005];

void solve1() {
    ll mask = (1LL << 43LL) - 1;
    bool dp[n + 3][n + 3];
    for (ll b = 42; b >= 0; b--) {
        mask ^= (1LL << b);
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= i; k++) {
                for (int j = 0; j < i; j++) {
                    if (((mask | (qs[i] - qs[j])) == mask) && dp[j][k - 1]) dp[i][k] = 1;
                }
            }
        }
        bool pass = 0;
        for (int i = a; i <= b; i++) {
            if (dp[n][i]) {
                pass = 1;
                break;
            }
        }
        if (!pass) mask |= (1LL << b);
    }
    cout << mask;
}

void solve2() {
    ll mask = (1LL << 43LL) - 1;
    int dp[n + 3];
    for (ll b = 42; b >= 0; b--) {
        mask ^= (1LL << b);
        fill(dp, dp + n + 1, 100000);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if ((mask | (qs[i] - qs[j])) == mask) dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        bool pass = 0;
        if (dp[n] <= b) pass = 1;
        if (!pass) mask |= (1LL << b);
    }
    cout << mask;
}


int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) cin >> y[i], qs[i] = qs[i - 1] + y[i];
    if (a != 1) {
        solve1();
    } else {
        solve2();
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…