제출 #1321655

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

#define int long long

constexpr int N = 105;
constexpr int inf = 1e13;

int a[N], s[N][N];
set<int> dp[N][N];

int memo[N][N][N];

int solve(int l, int r, int x) {
    if (r - l + 1 < x) {
        return inf;
    }
    if (x == 1) {
        memo[l][r][x] = s[l][r];
        return s[l][r];
    }
    if (memo[l][r][x] != -1) {
        return memo[l][r][x];
    }
    int ret = inf;
    for (int i = l; i < r; i++) {
        for (int j = 1; j < x; j++) {
            if (i - l + 1 >= j && r - i >= x - j) {
                ret = min(ret, (solve(l, i, j) | solve(i + 1, r, x - j)));
            }
        }
    }
    memo[l][r][x] = ret;
    return ret;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                memo[i][j][k] = -1;
            }
        }
    }
    int n, l, r;
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i <= n; i++) {
        int cur = 0;
        for (int j = i; j <= n; j++) {
            cur += a[j];
            s[i][j] = cur;
        }
    }
    int ans = inf;
    for (int i = l; i <= r; i++) {
        ans = min(ans, solve(1, n, i));
    }
    cout << ans << '\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...