Submission #976904

#	Time	Username	Problem	Language	Result	Execution time	Memory
976904		nnin	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	87 ms	31572 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pii pair<int,int>

int N, A, B;
ll sum[2005], dp[2005][2005];

bool check(ll x) {
    vector<pii> idx;
    idx.push_back({0, 0});
    for(int i=1;i<=N;i++) {
        int ct = 2e9;
        for(auto [j, ctt]:idx) {
            ll ss = sum[i]-sum[j];
            if((ss|x)==x && (ss&x)==ss) {
                ct = min(ct, ctt+1);
            }
        }
        if(ct!=2e9) idx.push_back({i, ct});
    }
    return (idx.back().first==N && idx.back().second<=B);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>N>>A>>B;
    for(int i=1;i<=N;i++) cin>>sum[i], dp[i][0] = sum[i] += sum[i-1];
    ll ans = (1ll<<51)-1;
    for(int i=50;i>=0;i--) {
        ans ^= (1ll<<i);
        if(!check(ans)) {
            ans ^= (1ll<<i);
        }
    }
    cout<<ans;
}

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

Compilation message (stderr)

sculpture.cpp: In function 'bool check(ll)':
sculpture.cpp:14:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |         for(auto [j, ctt]:idx) {
      |                  ^

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