Submission #699919

#	Time	Username	Problem	Language	Result	Execution time	Memory
699919		Abrar_Al_Samit	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	127 ms	428 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;

const int nax = 2001;
const int INF = 1e9;
int n, a, b;

long long ans;
int curBit;
int dp[nax];
int tree[nax];

bool good(long long S) {
  long long x = ans>>curBit;
  long long y = S>>curBit;

  return ((x&y)==y);
}
int solve(int i) {
  if(i>n) return 0;
  int &ret = dp[i];
  if(ret!=-1) return ret;
  ret = INF;

  long long S = 0;
  for(int k=i; k<=n; ++k) {
    S += tree[k];
    if(good(S)) {
      ret = min(ret, solve(k+1)+1);
    }
  }
  return ret;
}
void PlayGround() {
  cin>>n>>a>>b;
  for(int i=1; i<=n; ++i) {
    cin>>tree[i];
  }

  for(int i=44; i>=0; --i) {
    curBit = i;
    memset(dp, -1, sizeof dp);
    if(solve(1)>b) ans |= 1LL<<i;
  }
  cout<<ans<<'\n';

  // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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