Submission #199577

#	Time	Username	Problem	Language	Result	Execution time	Memory
199577		SamAnd	Holding (COCI20_holding)	C++17	110 / 110	102 ms	106360 KiB

holding

#include <bits/stdc++.h>
using namespace std;
const int N = 102;
const int INF = 1000000009;

int n, l, r, kk;
int a[N];

int dp[N][N][N * N / 4];

int main()
{
    scanf("%d%d%d%d", &n, &l, &r, &kk);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    kk = min(kk, (N * N / 4) - 1);
    int s = 0;
    for (int i = l; i <= r; ++i)
        s += a[i];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < N * N / 4; ++k)
                dp[i][j][k] = INF;
    dp[0][l - 1][0] = 0;
    for (int i = 0; i <= l - 1; ++i)
    {
        for (int j = l - 1; j <= r; ++j)
        {
            for (int k = 0; k <= kk; ++k)
            {
                if (k + 1 <= kk)
                    dp[i][j][k + 1] = min(dp[i][j][k + 1], dp[i][j][k]);
                if (i != l - 1)
                    dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
                if (j != r)
                    dp[i][j + 1][k] = min(dp[i][j + 1][k], dp[i][j][k] + a[j + 1]);
                if (i != l - 1 && j != r && k + abs(i + 1 - (j + 1)) <= kk)
                    dp[i + 1][j + 1][k + abs(i + 1 - (j + 1))] = min(dp[i + 1][j + 1][k + abs(i + 1 - (j + 1))],
                                                                     dp[i][j][k] + a[i + 1]);
            }
        }
    }
    dp[n + 1][r + 1][0] = 0;
    for (int i = n + 1; i >= r + 1; --i)
    {
        for (int j = r + 1; j >= l; --j)
        {
            for (int k = 0; k <= kk; ++k)
            {
                if (k + 1 <= kk)
                    dp[i][j][k + 1] = min(dp[i][j][k + 1], dp[i][j][k]);
                if (i != r + 1)
                    dp[i - 1][j][k] = min(dp[i - 1][j][k], dp[i][j][k]);
                if (j != l)
                    dp[i][j - 1][k] = min(dp[i][j - 1][k], dp[i][j][k] + a[j - 1]);
                if (i != r + 1 && j != l && k + abs(i - 1 - (j - 1)) <= kk)
                    dp[i - 1][j - 1][k + abs(i - 1 - (j - 1))] = min(dp[i - 1][j - 1][k + abs(i - 1 - (j - 1))],
                                                                     dp[i][j][k] + a[i - 1]);
            }
        }
    }
    int ans = s;
    for (int i = l - 1; i <= r; ++i)
    {
        for (int k = 0; k <= kk; ++k)
        {
            ans = min(ans, dp[l - 1][i][k] + dp[r + 1][i + 1][kk - k]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

holding.cpp: In function 'int main()':
holding.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &l, &r, &kk);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

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