Submission #1305592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305592		ulvix	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	162 ms	660 KiB

sculpture

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#ifdef ULVI
    #include "debug.hpp"
#else
    #define db(...)
    #define dbv(v)
    #define line()
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define enld endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll sz=2e5+100;
const ll mod=1e9+7;
const ll inf=1ll<<62;
template<class T>
using indexed_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll n,l,r;
vector<ll> v(2100),pref(2100);
vector<vector<ll>> dp1(110,vector<ll>(110));
vector<ll> dp2(2100);
ll f1(ll mask){
    dp1.assign(n+5,vector<ll>(r+5));
    dp1[0][0]=1;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=min(i,r);j++){
            for(ll k=j-1;k<i;k++){
                if(dp1[k][j-1] && !((pref[i]-pref[k])&~mask)){
                    dp1[i][j]=1;
                    break;
                }
            }
        }
    }
    for(ll i=l;i<=r;i++) if(dp1[n][i]) return 1;
    return 0;
}
ll f2(ll mask){
    dp2.assign(n+5,inf);
    dp2[0]=0;
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<i;j++) if(!((pref[i]-pref[j])&~mask)) dp2[i]=min(dp2[i],dp2[j]+1);
    }
    return l<=dp2[n] && dp2[n]<=r;
}
ll f(ll mask){
    return (l==1?f2(mask):f1(mask));
}
void solve(){
    cin>>n>>l>>r;
    for(ll i=1;i<=n;i++){
        cin>>v[i];
        pref[i]=pref[i-1]+v[i];
    }
    ll ans=(1ll<<61)-1;
    for(ll i=1ll<<60;i;i>>=1) if(f(ans&~i)) ans&=~i;
    cout<<ans<<'\n';
}

int main(){
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    // cin>>t;
    for(ll _=1;_<=t;_++){
        // cout<<"Scenario #"<<_<<":\n";
        solve();
    }
}

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