Submission #162240

#	Time	Username	Problem	Language	Result	Execution time	Memory
162240		rama_pang	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	377 ms	632 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>> General_DP;
vector<int> Special_DP;

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

int8_t GeneralDP(int n, int groups, lint mask) { // O(N ^ 3) for any L, R, finds if solution exists
    if (n == N) 
        return (L <= groups && groups <= R);
    if (n > N)
        return false;
    if (groups > R)
        return false;
    if (General_DP[n][groups] != -1)
        return General_DP[n][groups];
    
    int8_t &res = General_DP[n][groups] = 0;

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

int SpecialDP(int n, lint mask) { // O(N ^ 2) for L = 1, finds minimum number of groups
    if (n == N) 
        return 0;
    if (n > N)
        return N + 1;
    if (Special_DP[n] != -1)
        return Special_DP[n];

    int &res = Special_DP[n] = N + 1;    

    for (int i = n; i < N; i++) 
        if ((get(n, i) | mask) == mask) 
            res = min(res, 1 + SpecialDP(i + 1, mask));

    return res;
}

bool solve(lint mask) { // Check if it is possible to get beauty of a subset of mask
    if (L == 1) {
        Special_DP.assign(N, -1);
        return (SpecialDP(0, mask) <= R);
    } else { 
        General_DP.assign(N, vector<int8_t>(R + 1, -1));
        return GeneralDP(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))) 
            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: 29 / 29