Submission #487323

#	Time	Username	Problem	Language	Result	Execution time	Memory
487323		leaked	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	453 ms	262148 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);
}
bool check(vec<pii> &e){
    for(int i=0;i<n;i++) go[i].reset();
    for(auto &z : e) go[z.f][z.s]=1;
    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,vec<pii> &e,ll x){
    if(!check(e)) return -inf;
//    cout<<"OK "<<b<<' '<<x<<endl;
//    for(auto &z : e)
//        cout<<z.f<<' '<<z.s<<endl;
    if(b==0) return x;
    vec<pii> lft;
    for(auto &z : e){
        ll w=get(z.s,z.f);
        w>>=(b-1);w<<=(b-1);
        if((w|x)==x)
            lft.pb(z);
    }
    ll w=rec(b-1,lft,x);
    if(w!=-inf) return w;
    return rec(b-1,e,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];
    }
    vec<pii> e;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++)
            e.pb({j,i});
    }
    cout<<rec(lg,e,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: 0 / 29