Submission #150959

#TimeUsernameProblemLanguageResultExecution timeMemory
150959osaaateiasavtnlBali Sculptures (APIO15_sculpture)C++14
100 / 100
154 ms4344 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
const int N = 2001, LG = 50;
int n, L, R;
int a[N];
bool dp[N][N];
int mn[N];
bool check(int ban) {
    if (L == 1) {
        for (int i = 1; i <= n; ++i) {
            mn[i] = N;
            int sum = 0;
            for (int j = i; j >= 1; --j) {
                sum += a[j];
                if ((sum & ban) == 0) mn[i] = min(mn[i], mn[j - 1] + 1);
            }   
        }
        return mn[n] <= R;
    }
    else {
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            int sum = 0;
            for (int j = i; j >= 1; --j) {
                sum += a[j];
                if ((sum & ban) == 0) {
                    for (int k = 1; k <= n; ++k) {
                        dp[i][k] |= dp[j - 1][k - 1];
                    }   
                }   
            }   
        }
        for (int i = L; i <= R; ++i) if (dp[n][i]) return 1;
        return 0;
    }
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> L >> R;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int ban = 0;
    for (int b = LG - 1; b >= 0; --b) if (check(ban + (1ll << b))) ban += 1ll << b; 
    cout << (1ll << LG) - 1 - ban << '\n';
}   
#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...