oj.uz

Submission #464852

# Submission time Handle Problem Language Result Execution time Memory
464852 2021-08-14T10:20:06 Z TheScrasse Holding (COCI20_holding) C++17
110 / 110
 388 ms 15988 KB 
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#define maxm 10010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b;
ll l, r, dp[2][maxn][maxm];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> n >> l >> r >> m;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (i = l; i <= r; i++) {
        for (j = 1; j <= n; j++) {
            for (k = 0; k <= m; k++) {
                dp[1][j][k] = max(dp[0][j][k], dp[1][j - 1][k]);
                if (k >= 1) dp[1][j][k] = max(dp[1][j][k], dp[1][j][k - 1]);
                if ((j >= l && j <= r) || k < abs(j - i)) continue;
                dp[1][j][k] = max(dp[1][j][k], dp[0][j - 1][k - abs(j - i)] + a[i] - a[j]);
            }
        }

        for (j = 1; j <= n; j++) {
            for (k = 0; k <= m; k++) {
                dp[0][j][k] = dp[1][j][k];
                dp[1][j][k] = 0;
                // cout << dp[0][j][k] << ' ';
            }
            // cout << nl;
        }
        // cout << nl;
    }

    for (i = l; i <= r; i++) res += a[i];
    res -= dp[0][n][m];

    cout << res << nl;

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 7 ms 2124 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 7 ms 2124 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 804 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 94 ms 8148 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 7 ms 2124 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 804 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 94 ms 8148 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 844 KB Output is correct
18 Correct 2 ms 844 KB Output is correct
19 Correct 95 ms 8152 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 7 ms 2124 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 804 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 94 ms 8148 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 844 KB Output is correct
18 Correct 2 ms 844 KB Output is correct
19 Correct 95 ms 8152 KB Output is correct
20 Correct 5 ms 1740 KB Output is correct
21 Correct 4 ms 2124 KB Output is correct
22 Correct 1 ms 1100 KB Output is correct
23 Correct 10 ms 6988 KB Output is correct
24 Correct 13 ms 1632 KB Output is correct
25 Correct 388 ms 15988 KB Output is correct