Submission #869996

#TimeUsernameProblemLanguageResultExecution timeMemory
869996PagodePaivaThe short shank; Redemption (BOI21_prison)C++17
15 / 100
2055 ms510596 KiB
#include<bits/stdc++.h> #define pii pair <int, int> #define fr first #define sc second #define int long long #define N 4010 using namespace std; int range[N][N]; int v[N]; int dp[N][N]; int n, d, t; int solve(int l, int r){ if(l > r) return 0; if(range[l][r] != -1) return range[l][r]; if(v[l] > t) return range[l][r] = solve(l+1,r); int sum = t - v[l] + 1; int con = 1; for(int i = l+1;i < l+sum;i++){ if(i > r) break; if(v[i] <= v[l]+con){ return range[l][r] = con + solve(i, r); } con++; } return range[l][r] = con + solve(l+sum, r); } int32_t main(){ 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 pos = 1;pos <= n;pos++){ for(int qtd = 0;qtd <= d;qtd++){ dp[pos][qtd] = solve(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] + solve(i+1, pos)); } } } cout << dp[n][d] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...