Submission #250717

#	Time	Username	Problem	Language	Result	Execution time	Memory
250717		jovan_b	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	166 ms	504 KiB

sculpture

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

typedef long long ll;
typedef long double ld;

ll n, a, b;

bool moze[105][105];
ll niz[2005];
ll mn[2005];

bool check(ll k){
    if(a > 1){
        moze[0][0] = 1;
        for(ll i=1; i<=100; i++){
            for(ll j=0; j<=100; j++){
                moze[i][j] = 0;
            }
        }
        for(ll i=1; i<=n; i++){
            ll sum = 0;
            for(ll j=i; j>=1; j--){
                sum += niz[j];
                if((sum | k) == k){
                    for(ll turns=1; turns<=b; turns++){
                        moze[i][turns] |= moze[j-1][turns-1];
                    }
                }
            }
        }
        for(ll i=a; i<=b; i++) if(moze[n][i]) return 1;
        return 0;
    }
    for(ll i=1; i<=n; i++){
        mn[i] = b+5;
    }
    for(ll i=1; i<=n; i++){
        ll sum = 0;
        for(ll j=i; j>=1; j--){
            sum += niz[j];
            if((sum | k) == k){
                mn[i] = min(mn[i], mn[j-1]+1);
            }
        }
    }
    return mn[n] <= b;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    cin >> n >> a >> b;
    for(ll i=1; i<=n; i++){
        cin >> niz[i];
    }
    ll res = 0;
    for(ll j=50; j>=0; j--){
        if(!check(res+(1LL<<j)-1)) res += (1LL<<j);
    }
    cout << res;
    return 0;
}

/*
6 1 1
8 1 2 1 5 4
*/

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