Submission #198718

#	Time	Username	Problem	Language	Result	Execution time	Memory
198718		socho	Holding (COCI20_holding)	C++14	110 / 110	1506 ms	216444 KiB

holding

#include "bits/stdc++.h"
using namespace std;
 
const int MXN = 105;
int val[MXN];
const int MXK = 5005;
 
int dp[MXN][MXN][MXK];
 
int n, l, r, k;
 
int mincost(int pos, int at, int left_to_spend) {
    
    if (at == r + 1) {
        return (left_to_spend < 0 ? INT_MAX : 0);
    }
    
    if (pos >= n || left_to_spend < 0) {
        return INT_MAX;
    }
    
    if (dp[pos][at][left_to_spend] != -1) return dp[pos][at][left_to_spend];
    
    int take_cost = abs(pos - at);
    
    int mn = INT_MAX;
    
    if (left_to_spend >= take_cost) {
        int t = mincost(pos+1, at+1, left_to_spend - take_cost);
        if (t != INT_MAX) {
            mn = min(mn, val[pos] + t);
        }
    }
    int f = mincost(pos+1, at, left_to_spend);
    mn = min(mn, f);
    
    return dp[pos][at][left_to_spend] = mn;
    
}
 
 
int main() {
    
    for (int i=0; i<MXN; i++) {
        for (int j=0; j<MXN; j++) {
            for (int k=0; k<MXK; k++) {
                dp[i][j][k] = -1;
            }
        }
    }
    
    cin >> n >> l >> r >> k;
    l--; r--;
    k = min(k, 5000);
    
    for (int i=0; i<n; i++) cin >> val[i];
    
    cout << mincost(0, l, k) << endl;
    
}

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