제출 #699828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699828		Abrar_Al_Samit	Bali Sculptures (APIO15_sculpture)	C++17	21 / 100	1094 ms	472 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) {
  for(int j=curBit; j<44; ++j) {
    if((S>>j&1) && (~ans>>j&1)) return false;
  }
  return true;
}
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: 0 / 29