oj.uz

Submission #1075637

# Submission time Handle Problem Language Result Execution time Memory
1075637 2024-08-26T08:12:16 Z tradz Holding (COCI20_holding) C++14
110 / 110
 103 ms 204616 KB 
#include <bits/stdc++.h>

#define For(i,a,b) for(int i = a; i <= b; i++)
#define Ford(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define RRH(v) v.resize(unique(all(v)) - v.begin())

using namespace std;
const int  N = 1e6+7;
const int M = 1e9+7;
const ll oo = 3e18;

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

int dpL[102][102][2507];
int dpR[102][102][2507];

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

    #define TASK ""
    if (fopen (".inp", "r")) {
        freopen (".inp", "r", stdin);
        freopen (".out", "w", stdout);
    }
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    cin >> n >> l >> r >> k;
    memset(dpL, 0, sizeof dpL);
    memset(dpR, 0, sizeof dpR);
    For (i, 1, n) cin >> a[i];
    k = min(k, n * n / 4);
    int sum = 0;
    for (int i = l; i <= r; i++) sum += a[i];
    for (int i = 1; i < l; i++) {
        for (int j = l; j <= r; j++) {
            for (int h = 0; h <= k; h++) {
                dpL[i][j][h] = max(dpL[i - 1][j][h], dpL[i][j - 1][h]);
                if (h >= (j - i)) dpL[i][j][h] = max(dpL[i][j][h], dpL[i - 1][j - 1][h - j + i] + a[j] - a[i]);
            }
        }
    }

    for (int i = n; i > r; i--) {
        for (int j = r; j >= l; j--) {
            for (int h = 0; h <= k; h++) {
                dpR[j][i][h] = max(dpR[j + 1][i][h], dpR[j][i + 1][h]);
                if (h >= (i - j)) dpR[j][i][h] = max(dpR[j][i][h], dpR[j + 1][i + 1][h - i + j] + a[j] - a[i]);
            }
        }
    }

    int ans = 0;
    ans = max(dpL[l - 1][r][k], dpR[l][r + 1][k]);
    for (int i = l; i <= r; i++) {
        for (int h = 0; h <= k; h++) {
            ans = max(ans, dpL[l - 1][i][h] + dpR[i + 1][r + 1][k - h]);
        }
    }

    cout << sum - ans << '\n';

    return 0;
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:28:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen (".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holding.cpp:29:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen (".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
holding.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 204552 KB Output is correct
2 Correct 93 ms 204520 KB Output is correct
3 Correct 87 ms 204484 KB Output is correct
4 Correct 89 ms 204368 KB Output is correct
5 Correct 103 ms 204616 KB Output is correct
6 Correct 83 ms 204412 KB Output is correct
7 Correct 89 ms 204368 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 204552 KB Output is correct
2 Correct 93 ms 204520 KB Output is correct
3 Correct 87 ms 204484 KB Output is correct
4 Correct 89 ms 204368 KB Output is correct
5 Correct 103 ms 204616 KB Output is correct
6 Correct 83 ms 204412 KB Output is correct
7 Correct 89 ms 204368 KB Output is correct
8 Correct 100 ms 204372 KB Output is correct
9 Correct 92 ms 204368 KB Output is correct
10 Correct 85 ms 204476 KB Output is correct
11 Correct 86 ms 204372 KB Output is correct
12 Correct 91 ms 204464 KB Output is correct
13 Correct 95 ms 204564 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 204552 KB Output is correct
2 Correct 93 ms 204520 KB Output is correct
3 Correct 87 ms 204484 KB Output is correct
4 Correct 89 ms 204368 KB Output is correct
5 Correct 103 ms 204616 KB Output is correct
6 Correct 83 ms 204412 KB Output is correct
7 Correct 89 ms 204368 KB Output is correct
8 Correct 100 ms 204372 KB Output is correct
9 Correct 92 ms 204368 KB Output is correct
10 Correct 85 ms 204476 KB Output is correct
11 Correct 86 ms 204372 KB Output is correct
12 Correct 91 ms 204464 KB Output is correct
13 Correct 95 ms 204564 KB Output is correct
14 Correct 87 ms 204560 KB Output is correct
15 Correct 87 ms 204596 KB Output is correct
16 Correct 95 ms 204448 KB Output is correct
17 Correct 83 ms 204552 KB Output is correct
18 Correct 96 ms 204408 KB Output is correct
19 Correct 95 ms 204460 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 204552 KB Output is correct
2 Correct 93 ms 204520 KB Output is correct
3 Correct 87 ms 204484 KB Output is correct
4 Correct 89 ms 204368 KB Output is correct
5 Correct 103 ms 204616 KB Output is correct
6 Correct 83 ms 204412 KB Output is correct
7 Correct 89 ms 204368 KB Output is correct
8 Correct 100 ms 204372 KB Output is correct
9 Correct 92 ms 204368 KB Output is correct
10 Correct 85 ms 204476 KB Output is correct
11 Correct 86 ms 204372 KB Output is correct
12 Correct 91 ms 204464 KB Output is correct
13 Correct 95 ms 204564 KB Output is correct
14 Correct 87 ms 204560 KB Output is correct
15 Correct 87 ms 204596 KB Output is correct
16 Correct 95 ms 204448 KB Output is correct
17 Correct 83 ms 204552 KB Output is correct
18 Correct 96 ms 204408 KB Output is correct
19 Correct 95 ms 204460 KB Output is correct
20 Correct 87 ms 204372 KB Output is correct
21 Correct 88 ms 204372 KB Output is correct
22 Correct 83 ms 204372 KB Output is correct
23 Correct 88 ms 204372 KB Output is correct
24 Correct 90 ms 204612 KB Output is correct
25 Correct 102 ms 204372 KB Output is correct