Submission #1135606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135606		DangKhoizzzz	Holding (COCI20_holding)	C++20	110 / 110	18 ms	25156 KiB

holding

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define ar3 array <int , 3>

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 100 + 5;
const int maxk = 2507;

int n , a[maxn] , L , R , K;
int dpl[maxn][maxn][maxk];
int dpr[maxn][maxn][maxk];

void solve()
{
    cin >> n >> L >> R >> K;

    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = L; i <= R; i++)
    {
        for(int j = 1; j < L; j++)
        {
            for(int k = 1; k < maxk; k++)
            {
                dpl[i][j][k] = min(dpl[i-1][j][k] , dpl[i][j-1][k]);

                if(i - j <= k)
                {
                    dpl[i][j][k] = min(dpl[i][j][k] , dpl[i-1][j-1][k - (i - j)] + (a[j] - a[i]));
                }
            }
        }
    }

    for(int i = R; i >= L; i--)
    {
        for(int j = n; j > R; j--)
        {
            for(int k = 1; k < maxk; k++)
            {
                dpr[i][j][k] = min(dpr[i+1][j][k] , dpr[i][j+1][k]);

                if(j - i <= k)
                {
                    dpr[i][j][k] = min(dpr[i][j][k] , dpr[i+1][j+1][k - (j - i)] + (a[j] - a[i]));
                }
            }
        }
    }

    int sum = accumulate(a+L , a+R+1 , 0);
    int ans = sum;

    for(int i = L-1; i <= R; i++)
    {
        int mn = 0;

        for(int j = K; j >= 0; j--)
        {
            mn = min(mn , dpr[i+1][R+1][K - j]);
            ans = min(ans , sum + (dpl[i][L-1][j] + mn));
        }
    }

    cout << ans << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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