Submission #976923

#	Time	Username	Problem	Language	Result	Execution time	Memory
976923		nnin	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	199 ms	688 KiB

sculpture

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

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

bool check(ll x) {
    vector<piv> idx;
    idx.push_back({0, {0}});
    for(int i=1;i<=N;i++) {
        set<int> tmp;
        for(auto [j, s]:idx) {
            ll ss = sum[i]-sum[j];
            if((ss|x)==x && (ss&x)==ss) {
                for(int ctt:s) if(ctt<B) tmp.insert(ctt+1);
            }
        }
        if(!tmp.empty()) idx.push_back({i, tmp});
    }
    if(idx.back().first<N) return false;
    for(int s:idx.back().second) if(s>=A && s<=B) return true;
    return false;
}

bool check1(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], sum[i] += sum[i-1];
    ll ans = (1ll<<51)-1;
    for(int i=50;i>=0;i--) {
        ans ^= (1ll<<i);
        if((A>1 && !check(ans)) || (A==1 && !check1(ans))) {
            ans ^= (1ll<<i);
        }
    }
    cout<<ans;
}

Compilation message (stderr)

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

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