Submission #1314319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314319		al95ireyiz	Holding (COCI20_holding)	C++20	88 / 110	2094 ms	4532 KiB

holding

#pragma GCC optimize("Ofast", "unroll-loops", "fast-math", "no-stack-protector")
#pragma GCC option("arch=native")
#pragma GCC target("avx", "avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 2e5 + 5;
ll n, m, k = 0;

ll a[105], memo[5005][105];
void _() {
  // r = n subtasklari

  // Observation: eger range icinden cixaracagin ve range icine getireceyin indexleri secsen bes edir
  // cunki cost onlarin yerini nece deyissen de eyni qalir (eger rangeden eyni terefdedise)

  // n <= 13 subtaski ucun onda sadece range icinden max k dene element secsek colden optimal olan k dene
  // elementi secmek ucun bitmask ata bilerik cunki en pis halda n / 2 dene element secmeliyik range colunden.
  // Cunki, (k <= min(length of range, n - length of range)) max qiymeti ucun length of range = n / 2,
  // O(2^12) = O(4096), o da rahatliqla kecir.
  // Rahatliqla olmasa da kecdi(Sliding Windows)

  // n <= 50 subtaski ucun bitmask ata bilmerem, dp elemeliyem necese

  // Observation: Max lazim olan cost n <= 100 ucun bele 5000-den cox deyil

  ll l, r;
  cin >> n >> l >> r >> m;
  m = min(m, 5000ll);
  l --, r --;
  for(ll i = 0; i < n; i ++){
    cin >> a[i];
  }
  ll sz = n / 2, sz_ = n - n / 2, le = r - l + 1, cv = inf;

  for(ll cs = 0; cs <= m; cs ++){
    for(ll ct = 0; ct <= le; ct ++){
      memo[cs][ct] = inf;
    }
  }
  {
    ll cm = 0;
    for(ll i = l; i <= r; i ++) cm += a[i];
    memo[0][le] = cm;
  }
  for(ll msk = 0; msk < (1ll << sz); msk ++){
    if(__builtin_popcount(msk) > le) continue;
    ll cost = 0, sum = 0, ind = l, x = msk;
    while(x){
      ll nd = __builtin_ctz(x);
      sum += a[nd];
      cost += abs(nd - ind);
      ind ++;
      x &= x - 1;
    }
    // for(ll i = 0; i < sz; i ++){
    //   if(msk & (1ll << i)){
    //     sum += a[i];
    //     cost += abs(i - ind);
    //     if(cost > m) break;
    //     ind ++;
    //   }
    // }
    if(cost <= m){
      memo[cost][__builtin_popcount(msk)] = min(memo[cost][__builtin_popcount(msk)], sum);
    }
  }

  for(ll cs = 1; cs <= m; cs ++){
    for(ll ct = 0; ct <= le; ct ++){
      memo[cs][ct] = min(memo[cs][ct], memo[cs - 1][ct]);
    }
  }
  for(ll msk_ = 0; msk_ < (1ll << sz_); msk_ ++){
    if(__builtin_popcount(msk_) > le) continue;
    ll cost = 0, sum = 0, ind = r - __builtin_popcount(msk_) + 1, x_ = msk_;
    while(x_){
      ll nd = __builtin_ctz(x_);
      sum += a[nd + sz];
      cost += abs((nd + sz) - ind);
      ind ++;
      x_ &= x_ - 1;
    }
    // for(ll i_ = 0; i_ < sz_; i_ ++){
    //   if(msk_ & (1ll << i_)){
    //     sum += a[i_ + sz];
    //     cost += abs((i_ + sz) - ind);
    //     if(cost > m) break;
    //     ind ++;
    //   }
    // }
    if(cost <= m){
      cv = min(cv, memo[m - cost][le - __builtin_popcount(msk_)] + sum);
    }
  }
  cout << cv << '\n';
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t = 1;
  // cin >> t;
  while(t --) _();
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 0 / 22