Submission #487325

#	Time	Username	Problem	Language	Result	Execution time	Memory
487325		leaked	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	371 ms	964 KiB

sculpture

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N=2e3+2;
const int lg=61;
const ll inf=1e18;
int dp1[N],n,a,b;
bitset<N> dp[N];
bitset<N> go[N];
ll pref[N];
ll get(int l,int r){
    return pref[r]-(l?pref[l-1]:0);
}
vec<pii> e;
bool check(){
    if(n>500){
        for(int i=0;i<=n;i++) dp1[i]=1e9;
        dp1[0]=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                if(go[i][j])
                    umin(dp1[i+1],dp1[j]+1);
            }
        }
        return (dp1[n]<=b);
    }
    else{
        for(int i=0;i<=n;i++){
            dp[i].reset();
        }
        dp[0][0]=1;
        for(int i=0;i<n;i++){
            for(int cnt=n;cnt>=0;cnt--){
                int is=(dp[cnt]&go[i]).count();
                if(is)
                    dp[cnt+1][i+1]=1;
            }
        }
        int ok=0;
        for(int i=a;i<=b;i++)
            ok|=(dp[i][n]==1);
        return ok;
    }
}
ll rec(int b,ll x){
    for(int i=0;i<n;i++){
        go[i].reset();
        for(int j=0;j<=i;j++){
            ll w=get(j,i);
            w>>=(b);w<<=(b);
            if((w|x)==x)
                go[i][j]=1;
        }
    }
    if(!check()) return -inf;
    if(b==0) return x;
//    cout<<"OK "<<b<<' '<<x<<endl;
//    for(auto &z : e)
//        cout<<z.f<<' '<<z.s<<endl;
    if(b==0) return x;
    ll w=rec(b-1,x);
    if(w!=-inf) return w;
    return rec(b-1,x+pw(b-1));
}
signed main(){
    fast_iati;
    cin>>n>>a>>b;
    for(int i=0;i<n;i++){
        cin>>pref[i];
        if(i)
            pref[i]+=pref[i-1];
    }
    cout<<rec(lg,0);
    return 0;
}
/*
6 1 3
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