제출 #1314304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314304		al95ireyiz	Holding (COCI20_holding)	C++20	0 / 110	3 ms	4408 KiB

holding

#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;
  l --, r --;
  for(ll i = 0; i < n; i ++){
    cin >> a[i];
  }

  memset(memo, 0x3f3f3f, sizeof(memo));
  ll sz = n / 2, le = r - l + 1;
  {
    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 - 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 ct = 0; ct <= 100; ct ++){
    for(ll cs = 1; cs <= 5000; cs ++){
      memo[cs][ct] = min(memo[cs][ct], memo[cs - 1][ct]);
    }
  }
  ll sz_ = n - sz, cv = inf;
  for(ll msk_ = 0; msk_ < (1ll << sz_); msk_ ++){
    if(__builtin_popcount(msk_) > le) continue;
    ll cost = 0, sum = 0, ind = r;
    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 << cost << ' ' << sum << ' ' << le - __builtin_popcount(msk_) << '\n';
  }
  cout << cv << '\n';
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t = 1;
  // cin >> t;
  while(t --) _();
}

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