Submission #1191809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191809		emad234	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	143 ms	448 KiB

sculpture

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 2e3 + 5;
using namespace std;
int a[mxN],dp[mxN],n,A,B;
int solve(int val){
  memset(dp,0,sizeof dp);
  for(int i = 1;i <= n;i++){
    int num = 0;
    dp[i] = 1e18;
    for(int j = i;j;j--){
      num += a[j];
      if(!(num & val)) dp[i] = min(dp[i],dp[j - 1] + 1);
    }
  }
  return dp[n];
}
int solve1(int val){
  memset(dp,0,sizeof dp);
  for(int i = 1;i <= n;i++){
    int num = 0;
    dp[i] = 0;
    for(int j = i;j;j--){
      num += a[j];
      if(!(num & val)) dp[i] = max(dp[i],dp[j - 1] + 1);
    }
  }
  return dp[n];
}
signed main(){
  cin >>n>>A>>B;
  for(int i = 1;i <= n;i++) cin >>a[i];
  int ans = 0;
  for(int bt = 45;bt >= 0;bt--){
    int val = ans + (1LL << bt);
    int bg = 1;
    int num = 0;
    if(solve(val) <= B && solve1(val) >= A) ans += (1LL << bt);
  }
  // cout<<ans<<' ';
  cout<< (ans ^ ((1LL << 46) - 1));
}

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