Submission #1183394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183394		al95ireyiz	Holding (COCI20_holding)	C++20	88 / 110	2093 ms	8660 KiB

holding

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
#define ll long long
#define love 0
const ll INF = 1e9;
const ll INFL = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 100 + 5;
ll n, m, k = 0;
ll l, r, d, a[maxn];
const ll maxn2 = 10000 + 5;
ll mp[maxn][maxn2];
void _(){
    cin >> n >> l >> r >> d;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    for (ll i = 0; i < maxn; i++)
        for (ll j = 0; j < maxn2; j++)
            mp[i][j] = INF;
    ll l1 = n / 2, l2 = n - n / 2;
    for (ll i = 0; i < (1LL << l1); i++) {
        ll say = __builtin_popcountll(i);
        if (say > r - l + 1)
            continue;
        ll nw = l, cm = 0, tmp = 0;
        ll mask = i;
        while (mask) {
            int j = __builtin_ctzll(mask);
            mask &= mask - 1;
            tmp += abs(nw - (j + 1));
            cm += a[j + 1];
            nw++;
            if (tmp > d)
                break;
        }
        if (tmp <= d)
            mp[say][tmp] = min(mp[say][tmp], cm);
    }
    for (ll i = 0; i < maxn; i++) {
        for (ll j = 1; j < maxn2; j++)
            mp[i][j] = min(mp[i][j], mp[i][j - 1]);
    }
    ll cv = INFL;
    for (ll i = 0; i < (1LL << l2); i++) {
        ll say = __builtin_popcountll(i);
        if (say > r - l + 1)
            continue;
        ll ot = (r - l + 1) - say;
        ll nw = l + ot, cm = 0, tmp = 0;
        ll mask = i;
        while (mask) {
            int j = __builtin_ctzll(mask);
            mask &= mask - 1;
            tmp += abs(nw - (j + 1 + l1));
            cm += a[j + 1 + l1];
            nw++;
            if (tmp > d)
                break;
        }
        if (tmp <= d)
            cv = min(cv, mp[ot][d - tmp] + cm);
    }
    cout << cv << "\n";
}
signed main(){
    auto testcaseruntime = clock();
    cin.tie(0)->sync_with_stdio(0);
    ll t = 1;
    while (t--) {
        _();
    }
    cerr << "\n\033[1;31mTime: \033[1;30m" 
         << (double)(clock() - testcaseruntime) / 1000000 
         << "\033[1;32m seconds\n";
}

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