oj.uz

Submission #930408

# Submission time Handle Problem Language Result Execution time Memory
930408 2024-02-19T14:49:34 Z Whisper Holding (COCI20_holding) C++17
110 / 110
 64 ms 200224 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using str = string;
using ld = long double;
using T = tuple<ll, ll, ll>;

// #define int long long
#define Base 31
#define sz(a) (int)a.size()
#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 REP(i, n) for ( int i = 0 ; i < n ; ++i )
#define REPD(i, n) for ( int i =  n - 1 ; ~(--i) ; )
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

constexpr ll LINF = (1ll << 62);
constexpr int INF = (1ll << 30);
constexpr int MAX = 1e2 + 1;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

const int MAXK = 100 * 100 / 4 + 1;
int l[MAX][MAX][MAXK];
int r[MAX][MAX][MAXK];
int a[MAX];
int tot = 0;


int N, L, R, K;
void Whisper(){ 
    cin >> N >> L >> R >> K;
    FOR(i, 1, N) cin >> a[i];
    for (int i = L; i <= R; i++) tot += a[i];
    K = min(K, N * N / 4);
    memset(l, 0, sizeof l);
    memset(r, 0, sizeof r);
    //posIn = i, posOut = j

    for (int i = 1 ; i < L; i++){
        for (int j = L; j <= R; j++){
            for (int k = 0; k <= K; k++){
                l[i][j][k] = max(l[i - 1][j][k], l[i][j - 1][k]);
                if (k >= (j - i)) l[i][j][k] = max(l[i][j][k], l[i - 1][j - 1][k - (j - i)] + a[j] - a[i]);
            }
        }
    }
    for (int i = N; i >= R + 1; i--){
        for (int j = R; j >= L; j--){
            for (int k = 0; k <= K; k++){
                r[i][j][k] = max(r[i + 1][j][k], r[i][j + 1][k]);
                if (k >= (i - j)) r[i][j][k] = max(r[i][j][k], r[i + 1][j + 1][k - (i - j)] + a[j] - a[i]);
            }
        }
    }

    ll ans = 0;
    for (int i = L - 1; i <= R + 1; i++){
        for (int k = 0; k <= K; k++){
            ans = max(ans, 1ll * l[L - 1][i][k] + 1ll * r[R + 1][i + 1][K - k]);
        }
    }
    cout << tot - ans;
}                 

signed main(){
    setupIO();
    int Test = 1;
    // cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 200108 KB Output is correct
2 Correct 49 ms 200140 KB Output is correct
3 Correct 50 ms 200056 KB Output is correct
4 Correct 52 ms 200020 KB Output is correct
5 Correct 50 ms 199996 KB Output is correct
6 Correct 50 ms 200020 KB Output is correct
7 Correct 51 ms 199940 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 200108 KB Output is correct
2 Correct 49 ms 200140 KB Output is correct
3 Correct 50 ms 200056 KB Output is correct
4 Correct 52 ms 200020 KB Output is correct
5 Correct 50 ms 199996 KB Output is correct
6 Correct 50 ms 200020 KB Output is correct
7 Correct 51 ms 199940 KB Output is correct
8 Correct 50 ms 199972 KB Output is correct
9 Correct 51 ms 200020 KB Output is correct
10 Correct 51 ms 200000 KB Output is correct
11 Correct 50 ms 200016 KB Output is correct
12 Correct 51 ms 200104 KB Output is correct
13 Correct 51 ms 199984 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 200108 KB Output is correct
2 Correct 49 ms 200140 KB Output is correct
3 Correct 50 ms 200056 KB Output is correct
4 Correct 52 ms 200020 KB Output is correct
5 Correct 50 ms 199996 KB Output is correct
6 Correct 50 ms 200020 KB Output is correct
7 Correct 51 ms 199940 KB Output is correct
8 Correct 50 ms 199972 KB Output is correct
9 Correct 51 ms 200020 KB Output is correct
10 Correct 51 ms 200000 KB Output is correct
11 Correct 50 ms 200016 KB Output is correct
12 Correct 51 ms 200104 KB Output is correct
13 Correct 51 ms 199984 KB Output is correct
14 Correct 49 ms 200096 KB Output is correct
15 Correct 50 ms 200016 KB Output is correct
16 Correct 51 ms 200020 KB Output is correct
17 Correct 52 ms 200116 KB Output is correct
18 Correct 60 ms 200020 KB Output is correct
19 Correct 51 ms 200056 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 200108 KB Output is correct
2 Correct 49 ms 200140 KB Output is correct
3 Correct 50 ms 200056 KB Output is correct
4 Correct 52 ms 200020 KB Output is correct
5 Correct 50 ms 199996 KB Output is correct
6 Correct 50 ms 200020 KB Output is correct
7 Correct 51 ms 199940 KB Output is correct
8 Correct 50 ms 199972 KB Output is correct
9 Correct 51 ms 200020 KB Output is correct
10 Correct 51 ms 200000 KB Output is correct
11 Correct 50 ms 200016 KB Output is correct
12 Correct 51 ms 200104 KB Output is correct
13 Correct 51 ms 199984 KB Output is correct
14 Correct 49 ms 200096 KB Output is correct
15 Correct 50 ms 200016 KB Output is correct
16 Correct 51 ms 200020 KB Output is correct
17 Correct 52 ms 200116 KB Output is correct
18 Correct 60 ms 200020 KB Output is correct
19 Correct 51 ms 200056 KB Output is correct
20 Correct 56 ms 199924 KB Output is correct
21 Correct 50 ms 199980 KB Output is correct
22 Correct 52 ms 200016 KB Output is correct
23 Correct 55 ms 200224 KB Output is correct
24 Correct 56 ms 200020 KB Output is correct
25 Correct 61 ms 200016 KB Output is correct