Submission #543997

#	Time	Username	Problem	Language	Result	Execution time	Memory
543997		AlperenT	Holding (COCI20_holding)	C++17	110 / 110	169 ms	16516 KiB

holding

#include <bits/stdc++.h>

using namespace std;

const long long N = 100 + 5, K = 1e4 + 5, INF = 2e18 + 5;

long long n, l, r, k, arr[N], dp[N][K], prefix[N][K], suffix[N][K], ans = INF;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> l >> r >> k;

    for(int i = 1; i <= n; i++) cin >> arr[i];

    for(int i = 0; i < N; i++){
        for(int j = 0; j < K; j++){
            dp[i][j] = INF;
        }
    }

    dp[0][0] = 0;

    for(int i = 1; i <= n; i++){
        for(int rcnt = i; rcnt >= 0; rcnt--){
            for(int j = k; j >= 0; j--){
                if(rcnt > 0 && j >= rcnt) dp[rcnt][j] = min(dp[rcnt][j - rcnt], dp[rcnt - 1][j] + arr[i]);
                else if(rcnt > 0 && j < rcnt) dp[rcnt][j] = dp[rcnt - 1][j] + arr[i];
                else if(j >= rcnt) dp[rcnt][j] = dp[rcnt][j - rcnt];
            }
        }

        if(i >= l && i <= r){
            for(int j = 0; j <= k; j++) prefix[i][j] = dp[i - l + 1][j];
            for(int j = 1; j <= k; j++) prefix[i][j] = min(prefix[i][j], prefix[i][j - 1]);
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < K; j++){
            dp[i][j] = INF;
        }
    }

    dp[0][0] = 0;

    for(int i = n; i >= 1; i--){
        for(int rcnt = i; rcnt >= 0; rcnt--){
            for(int j = k; j >= 0; j--){
                if(rcnt > 0 && j >= rcnt) dp[rcnt][j] = min(dp[rcnt][j - rcnt], dp[rcnt - 1][j] + arr[i]);
                else if(rcnt > 0 && j < rcnt) dp[rcnt][j] = dp[rcnt - 1][j] + arr[i];
                else if(j >= rcnt) dp[rcnt][j] = dp[rcnt][j - rcnt];
            }
        }

        if(i >= l && i <= r){
            for(int j = 0; j <= k; j++) suffix[i][j] = dp[r - i + 1][j];
            for(int j = 1; j <= k; j++) suffix[i][j] = min(suffix[i][j], suffix[i][j - 1]);
        }
    }

    for(int i = l - 1; i <= r; i++){
        for(int j = 0; j <= k; j++){
            ans = min(ans, prefix[i][j] + suffix[i + 1][k - j]);
        }
    }

    cout << ans;
}

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