Submission #970457

#	Time	Username	Problem	Language	Result	Execution time	Memory
970457		NotLinux	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	2020 ms	135508 KiB

prison

//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 4010;
 
int range[N][N];
int v[N];
int dp[N][N];
int n, d, t;
 
void solve(){
    cin >> n >> d >> t;
    memset(range, -1, sizeof range);
 
    for(int i = 1;i <= n;i++) cin >> v[i];
 
    for(int i = 0;i <= d;i++){
        dp[0][i] = 0;
    }
 
    for(int d = 0;d <= n;d++){
        for(int l = 1;l <= n;l++){
            int r = l+d;
            if(r > n) continue;
                if(v[l] > t) {range[l][r] = (l == r ? 0 : range[l+1][r]); continue;}
                int sum = t - v[l] + 1;
                int con = 1;
                bool piroca = false;
                for(int i = l+1;i < l+sum;i++){
                    if(i > r) break;
                    if(v[i] <= v[l]+con){
                        range[l][r] = con + range[i][r];
                        piroca = true;
                        break;
                    }    
                    con++;
                }
 
                if(piroca) continue;
 
                range[l][r] = con + (l+sum > r ? 0 : range[l+sum][r]);
        }
    }
 
    for(int pos = 1;pos <= n;pos++){
        for(int qtd = 0;qtd <= d;qtd++){
            dp[pos][qtd] = range[1][pos];
            if(qtd == 0) continue;
            for(int i = pos-1;i >= 0;i--){
                dp[pos][qtd] = min(dp[pos][qtd], dp[i][qtd-1] + range[i+1][pos]);
            }
        }
    }
 
    cout << dp[n][d] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int testcase = 1;//cin >> testcase;
    while(testcase--)solve();
    cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20