Submission #680585

#	Time	Username	Problem	Language	Result	Execution time	Memory
680585		MtSaka	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	98 ms	468 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll n,l,r;cin>>n>>l>>r;
  vector<ll>a(n);
  for(auto&i:a)cin>>i;
  ll ans=0;
  auto calc=[&](ll bit)->bool {
    if(l==1){
      vector<ll>dp(n+1,INT_MAX);
      dp[0]=0;
      for(ll i=1;i<=n;i++){
        ll sum=0;
        for(ll j=i-1;j>=0;j--){
          sum+=a[j];
          if((sum&bit)==sum)dp[i]=min(dp[i],dp[j]+1);
        }
      }
      return dp[n]<=r;
    }
    vector dp(n+1,vector<ll>(n+1,0));
    dp[0][0]=1;
    for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){
      ll sum=0;
      for(ll k=j-1;k>=0;k--){
        sum+=a[k];
        if((sum&bit)==sum)dp[i][j]|=dp[i-1][k];
      }
    }
    for(ll i=l;i<=r;i++)if(dp[i][n])return true;
    return false;
  };
  for(ll i=40;i>=0;i--){
    if(!calc(ans+(1LL<<i)-1))ans|=(1LL<<i);
  }
  cout<<ans<<endl;
}

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