Submission #699812

#	Time	Username	Problem	Language	Result	Execution time	Memory
699812		Abrar_Al_Samit	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	313 ms	460 KiB

sculpture

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

const int nax = 101;
int n, a, b;

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

bool good(long long S) {
  if(S>>curBit&1) return false;
  for(int j=curBit+1; j<60; ++j) {
    if((S>>j&1) && (~ans>>j&1)) return false;
  }
  return true;
}
int solve(int i, int j) {
  if(i>n) return j>=a && j<=b;
  int &ret = dp[i][j];
  if(ret!=-1) return ret;
  ret = 0;

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

  for(int i=59; i>=0; --i) {
    curBit = i;
    memset(dp, -1, sizeof dp);
    if(!solve(1, 0)) 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: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 0 / 29