oj.uz

Submission #699824

# Submission time Handle Problem Language Result Execution time Memory
699824 2023-02-18T05:18:47 Z Abrar_Al_Samit Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 104 ms 32248 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = 2001;
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<44; ++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;
  int mx = -1;
  for(int k=i; k<=n; ++k) {
    S += tree[k];
    if(good(S)) ret |= solve(k+1, j+1), mx = k;
  }
  if(ret) assert(solve(mx+1, j+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, 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 32248 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 32240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 32192 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 32224 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 32228 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -