제출 #1350667

#제출 시각아이디문제언어결과실행 시간메모리
1350667bakhtiyarnBali Sculptures (APIO15_sculpture)C++20
50 / 100
318 ms52092 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2000+5;
int a[N], pre[N];
int dp[N][N];

// for(int i=1; i<=n; i++) 
void solve(){
  int n, L, R; cin >> n >> L >> R;
  for(int i=1; i<=n; i++) cin >> a[i], pre[i] = pre[i-1] + a[i];
  
  
  int cur = 0;
  for(int b=60; b>=0; b--){
    for(int i=1; i<=n; i++) for(int g=1; g<=R; g++) dp[i][g] = 0; dp[0][0]=1;
    cur += (1ll<<b)-1;
    
    // 
      int has = 0;
      
      vector<vector<int>> CAN(n+1);
      
      for(int i=1; i<=n; i++){
        for(int j=i; j>=1; j--){
          int sm = pre[i] - pre[j-1];
          if((sm|cur) != cur) continue;
          CAN[i].push_back(j);
        }
      }
      vector<int> mn(n+1, R+1);
      mn[0] = 0;
      
      for(int i=1; i<=n; i++){
        // for(int g=1; g<=R; g++){
          for(int j: CAN[i]){
            dp[i][mn[j-1]+1] = 1;
            mn[i] = min(mn[i], mn[j-1]+1);
            // dp[i][g] |= dp[j-1][g-1];
            // if(dp[i][g]) break;
          }
        // }
        
      }
      
      for(int g=L; g<=R; g++) has |= dp[n][g];
      
      
      if(!has) cur += (1ll<<b);
    // 
    
    
    cur -= (1ll<<b)-1;
  }
  
  cout << cur;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...