제출 #1183377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183377		al95ireyiz	Holding (COCI20_holding)	C++20	22 / 110	2093 ms	8660 KiB

holding

//*** Bismillah ***//
// It's the evening of another day. And the end of mine...
#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];
    {
        // 1st subtask success
        // mask :
        // 1 -> select, 2 -> dont select
        // ll cv = INF;
        // for(ll i=1;i<(1<<n);i++){
        //     if(__builtin_popcountll(i) != r - l + 1) continue;
        //     ll nw = l, tmp=0, cm = 0;
        //     for(ll j=0;j<n;j++){
        //         if(i&(1<<j)){
        //             tmp += abs(nw - (j+1));
        //             cm += a[j+1];
        //             nw ++;
        //         }
        //     }
        //     if(tmp <= d){
        //         cv = min(cv, cm);
        //     }
        // }
        // cout<<cv<<'\n';
    }
    // Optimization for subtask 2 and maybe 3:
    // Meet-in-the-middle
    // half mask + half mask
    // [1, n/2] <-> [n/2+1, n]
    // total r - l + 1 nums
    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<(1<<l1);i++){
        ll say = __builtin_popcountll(i);
        if(say > r - l + 1) continue;
        ll nw = l, cm = 0, tmp = 0;
        for(ll j=0;j<l1;j++){
            if(i&(1<<j)){
                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<(1<<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;
        for(ll j=0;j<l2;j++){
            if(i&(1<<j)){
                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;
    // cin>>t;
    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: 0 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 22