Submission #1350643

#TimeUsernameProblemLanguageResultExecution timeMemory
1350643bakhtiyarnBali Sculptures (APIO15_sculpture)C++20
46 / 100
1098 ms107372 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<unordered_set<long long>> dp(n+1);
  dp[0].insert(0);
  long long mn = 1e18;
  for(int g=1; g<=R; g++){
    vector<unordered_set<long long>> n_dp(n+1);
    for(int i=n; i>=1; i--){
      long long sm = 0;
      
      for(int j=i; j>=1; j--){
        sm += a[j];
        for(long long OR: dp[j-1]){
          if((sm|OR) > mn) continue;
          n_dp[i].insert(sm | OR);
        }
      }
      
      vector<int> kp;
      for(int OR1: dp[i]){
        bool ok = true;
        for(int OR2: dp[i]){
          if(OR1 == OR2) continue;
          if((OR1&OR2) == OR2) {
            ok = false;
            break;
          }
        }
        kp.push_back(OR1);
      }
      dp[i].clear();
      for(int OR1: kp) dp[i].insert(OR1);
      
      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...