Submission #846101

#	Time	Username	Problem	Language	Result	Execution time	Memory
846101		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	61 ms	600 KiB

sculpture

//LaziChicken - 9/2023

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

#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define fi first
#define se second
#define dim 3
#define tii tuple <int, int, int>
#define inf 0x3f

const ll nx = 2e3+2;
const ll bx = 1e3+2;
const ll mod = 1e9+7;

//--------------------------------
int n, p, q;
ll a, sum[nx];

ll range(int l, int r){
    return sum[r] - sum[l-1];
}

bool dp[102][102];
void sub4(){
    ll res = (1LL << 37) - 1;
    for (int bit = 36; bit >= 0; bit--){
        res ^= (1LL << bit);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++){
            for (int k = 1; k <= q; k++){
                for (int j = 1; j <= i; j++){
                    if ((res | range(j, i)) == res){
                        dp[i][k] |= dp[j-1][k-1];
                    }
                }
            }
        }
        bool ok = 0;
        for (int i = p; i <= q; i++){
            ok |= dp[n][i];
        }
        if (!ok) res ^= (1LL << bit);
    }
    cout << res;
    exit(0);
}

int f[nx];
void sub5(){
    ll res = (1LL << 41) - 1;
    for (int bit = 40; bit >= 0; bit--){
        res ^= (1LL << bit);
        memset(f, inf, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= i; j++){
                if ((range(j, i) | res) == res){
                    f[i] = min(f[i], f[j-1] + 1);
                }
            }
        }
        if (f[n] > q) res ^= (1LL << bit);
    }
    cout << res;
    exit(0);
}

//--------------------------------
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++){
        cin >> a;
        sum[i] = sum[i-1] + a;
    }
    if (n <= 100) sub4();
    else sub5();
}
/*
Note:

*/

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