oj.uz

Submission #1086138

# Submission time Handle Problem Language Result Execution time Memory
1086138 2024-09-09T15:53:51 Z tfgs Holding (COCI20_holding) C++17
110 / 110
 21 ms 25180 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }

const int N = 100;
int dpl[N][N][N*N/4], dpr[N][N][N*N/4];

void solve() {
    int n, l, r, k;
    cin >> n >> l >> r >> k; l--;
    ckmin(k, N*N/4-1);
    vi a(n);
    for (int& i : a) cin >> i;

    for (int pos_in = l; pos_in < r; pos_in++) {
        for (int pos_out = 0; pos_out < l; pos_out++) {
            for (int money = 0; money <= k; money++) {
                int& x = dpl[pos_in][pos_out][money];
                if (pos_in > l) {
                    ckmax(x, dpl[pos_in-1][pos_out][money]);
                }
                if (pos_out > 0) {
                    ckmax(x, dpl[pos_in][pos_out-1][money]);
                }
                if (money >= pos_in-pos_out) {
                    int prv_state = 0;
                    if (pos_in > l && pos_out > 0) {
                        prv_state = dpl[pos_in-1][pos_out-1][money-(pos_in-pos_out)];
                    }
                    ckmax(x, prv_state+a[pos_in]-a[pos_out]);
                }
                // ps(pos_in, pos_out, money, x);
            }
        }
    }
    
    for (int pos_in = r-1; pos_in >= l; pos_in--) {
        for (int pos_out = r; pos_out < n; pos_out++) {
            for (int money = 0; money <= k; money++) {
                int& x = dpr[pos_in][pos_out][money];
                if (pos_in < r) {
                    ckmax(x, dpr[pos_in+1][pos_out][money]);
                }
                if (pos_out > r) {
                    ckmax(x, dpr[pos_in][pos_out-1][money]);
                }
                if (pos_out-pos_in <= money) {
                    int prv_state = 0;
                    if (pos_in < r && pos_out > r) {
                        prv_state = dpr[pos_in+1][pos_out-1][money-(pos_out-pos_in)];
                    }
                    ckmax(x, prv_state+a[pos_in]-a[pos_out]);
                }
                // ps(pos_in, pos_out, money, x);
            }
        }
    }

    int ans = 0;
    for (int i = l-1; i < r; i++) {
        for (int money = 0; money <= k; money++)  {
            int res = 0;
            if (i >= l) {
                res += dpl[i][l-1][money];
            }
            if (i+1 < r) {
                res += dpr[i+1][n-1][k-money];
            }
            ckmax(ans, res);
        }
    }

    int interval_sum = 0;
    for (int i = l; i < r; i++) interval_sum += a[i];
    cout << interval_sum-ans << '\n';
}

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 860 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 2 ms 3160 KB Output is correct
12 Correct 1 ms 2140 KB Output is correct
13 Correct 6 ms 6748 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 2 ms 3160 KB Output is correct
12 Correct 1 ms 2140 KB Output is correct
13 Correct 6 ms 6748 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1628 KB Output is correct
17 Correct 1 ms 1628 KB Output is correct
18 Correct 2 ms 2908 KB Output is correct
19 Correct 5 ms 6560 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 2 ms 3160 KB Output is correct
12 Correct 1 ms 2140 KB Output is correct
13 Correct 6 ms 6748 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1628 KB Output is correct
17 Correct 1 ms 1628 KB Output is correct
18 Correct 2 ms 2908 KB Output is correct
19 Correct 5 ms 6560 KB Output is correct
20 Correct 4 ms 5980 KB Output is correct
21 Correct 2 ms 2908 KB Output is correct
22 Correct 2 ms 4444 KB Output is correct
23 Correct 2 ms 2392 KB Output is correct
24 Correct 6 ms 12120 KB Output is correct
25 Correct 21 ms 25180 KB Output is correct