Submission #844866

#	Time	Username	Problem	Language	Result	Execution time	Memory
844866		vjudge1	Holding (COCI20_holding)	C++17	110 / 110	55 ms	108600 KiB

holding

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
 
const int MAXN = 100 + 5;
const int MAXK = 10000 + 5;
const int INF = 1e9;

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #define OPEN freopen(".in", "r", stdin); \
                 freopen(".out", "w", stdout);
#else
    #define OPEN void(23);
#endif

int dp[MAXN][MAXN][MAXK / 4];

void solve()
{
    memset(dp, -1, sizeof(dp));
    int n, l, r, k; cin >> n >> l >> r >> k;
    vector <int> vec(n +1);
    for(int i = 1; i <= n; i++) cin >> vec[i];

    k = min(k, MAXK / 4);

    function <int(int, int, int)> f = [&](int x, int ind, int nw) -> int
    {
        if(ind > r +1) return INF;
        if(nw > k) return INF;
        if(x == n +1) return (ind == r +1 ? 0 : INF);
        int &it = dp[x][ind][nw];
        if(it != -1) return it;

        //cerr << x << " " << ind << " " << nw << "\n";
        int res = f(x +1, ind +1, nw + abs(ind - x)) + vec[x];
        res = min(res, f(x +1, ind, nw));

        return it = res;
    };

    cout << f(1, l, 0);

    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }
}

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