Submission #278821

#	Time	Username	Problem	Language	Result	Execution time	Memory
278821		jainbot27	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	157 ms	536 KiB

sculpture

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

using ll = long long;
#define f first
#define s second
const int N = 2001;
int dp[N], a[N], n, aa, b;
ll mx = 0, p[N];

bool works(int bit){
    //cerr << "BIT " << bit << "\n";
    ll most = mx + (1LL << bit);
    //cerr << "MOST " << most << "\n";
    for(int i=0; i<=n; i++){
        dp[i] = 1e9;
    }
    dp[0] = 0;
    for(int i=1; i <= n; i++){
        for(int j = 0; j < i; j++){
            ll sum = p[i] - p[j]; 
            if((sum|mx) < most){
                dp[i] = min(dp[i], dp[j] + 1);
            }
            //cerr << "(" << i << "," << j << ")" << " DP " << dp[i] << "\n";
        }
    }
    //cerr << "DP[N] " << dp[n] << "\n";
    return dp[n]>b;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> aa >> b;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        p[i] = p[i-1] + a[i];
    }
    for(int bit = 40; bit >= 0; bit--){
        if(works(bit)){
            mx += 1LL << bit;
        }
    }
    cout << mx << "\n";
}

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