Submission #1350635

#TimeUsernameProblemLanguageResultExecution timeMemory
1350635bakhtiyarnBali Sculptures (APIO15_sculpture)C++20
46 / 100
1098 ms56392 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 2000+5;
int a[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];
  
  vector<vector<long long>> dp(n+1);
  dp[0].push_back(0);
  long long mn = 1e18;
  for(int g=1; g<=R; g++){
    vector<vector<long long>> n_dp(n+1);
    for(int i=n; i>=1; i--){
      long long sm = 0;
      unordered_map<long long, bool> seen;
      for(int j=i; j>=1; j--){
        sm += a[j];
        for(long long OR: dp[j-1]){
          if((sm|OR) > mn) continue;
          if(seen[sm|OR]) continue;
          n_dp[i].push_back(sm | OR);
          seen[sm|OR] = true;
          // mn = min(mn, sm|OR);
        }
      }
      
      sort(dp[i].begin(), dp[i].end());
      
      vector<int> used(dp[i].size(), false);
      for(int j=0; j<dp[i].size(); j++){
        if(used[j]) continue;
        long long OR1 = dp[i][j];
        for(int k=j+1; k<dp[i].size(); k++){
          if(used[k]) continue;
          long long OR2 = dp[i][k];
          if((OR1 & OR2) == OR1) used[k] = true;
        }
      }
      
      vector<long long> saxla;
      for(int j=0; j<dp[i].size(); j++){
        if(!used[j]) saxla.push_back(dp[i][j]);
      }
      dp[i] = saxla;
      
      if(i == n and g >= L){
        for(long long OR: n_dp[n]) mn = min(mn, OR);
      }
    }
    swap(dp, n_dp);
    
    
  }
  
  
  cout << mn;
}

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...