제출 #162237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162237		rama_pang	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1061 ms	504 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

int N, L, R;
vector<lint> A;
vector<lint> prefix_sum;
vector<vector<int8_t>> DP;

inline lint get(int l, int r) {
    return prefix_sum[r] - ((l > 0)? prefix_sum[l - 1] : 0);
}

int8_t dp(int n, int groups, lint mask) {
    if (n == N) 
        return (L <= groups && groups <= R);
    if (n > N)
        return false;
    if (groups > R)
        return false;
    if (DP[n][groups] != -1)
        return DP[n][groups];
    
    int8_t &res = DP[n][groups];
    res = 0;

    for (int i = n; i < N; i++) 
        if ((get(n, i) | mask) == mask) 
            res |= dp(i + 1, groups + 1, mask);
    
    return res;
}

int8_t solve(lint mask) { // Check if it is possible to get beauty of a subset of mask
    DP.assign(N, vector<int8_t>(R, -1));
    return dp(0, 0, mask);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> L >> R;

    A.reserve(N), A.resize(N);
    prefix_sum.reserve(N), prefix_sum.resize(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        prefix_sum[i] = ((i > 0)? prefix_sum[i - 1] : 0) + A[i];
    }
    
    lint ans = (1ll << 62ll) - 1;
    for (lint bit = 61; bit >= 0; bit--) 
        if (solve(ans - (1ll << bit)) == 1) 
            ans -= (1ll << bit);
    
    cout << ans << "\n";

    return 0;
}

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