| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1314294 | al95ireyiz | Holding (COCI20_holding) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3", "unroll-loops", "fast-math", "no-stack-protector")
#pragma GCC target("avx", "avx2")
#pragma GCC option("arch=native")
#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;
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.
ll l, r, cm = 0;
cin >> n >> l >> r >> m;
vector<array<ll, 2>> v, v_;
for(ll i = 1, x; i <= n; i ++){
cin >> x;
if(l <= i and i <= r){
v.push_back({x, i});
cm += x;
} else{
v_.push_back({x, i});
}
}
ll cv = cm, sz = len(v), sz_ = len(v_);
for(ll msk = 0; msk < (1ll << sz); msk ++) for(ll msk_ = 0; msk_ < (1ll << sz_); msk_ ++){
if(__builtin_popcount(msk) != __builtin_popcount(msk_)) continue;
ll i = 0, i_ = 0, cost = 0, sum = cm;
while(i < sz and i_ < sz_){
while(i < sz and !(msk & (1ll << i))) i ++;
while(i_ < sz_ and !(msk_ & (1ll << i_))) i_ ++;
if(i < sz and i_ < sz_){
sum += - v[i][0] + v_[i_][0];
cost += abs(v[i][1] - v_[i_][1]);
i ++, i_ ++;
}
if(cost > m) break;
}
if(cost <= m) cv = min(cv, sum);
}
cout << cv << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
ll t = 1;
// cin >> t;
while(t --) _();
}