제출 #871438

#제출 시각아이디문제언어결과실행 시간메모리
871438Cyber_WolfThe short shank; Redemption (BOI21_prison)C++17
0 / 100
146 ms524292 KiB
#include <bits/stdc++.h> using namespace std; #define lg long long #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); const lg N = 505; lg n, d, tim; lg dp[N][N][N]; lg t[N]; int main() { fastio; cin >> n >> d >> tim; for(int i = 1; i <= n; i++) { cin >> t[i]; } d = min(n, d); memset(dp, 0x3f, sizeof(dp)); dp[0][0][d] = 0; t[0] = 1e18; for(int i = 1; i <= n; i++) { for(int j = 0; j <= d; j++) { lg mnm = t[i]; for(int k = i-1; k >= 0; k--) { mnm = min(mnm, t[k]+i-k); dp[i][i][j] = min(dp[i-1][k][j+1]+(t[i] <= tim), dp[i][i][j]); dp[i][k][j] = min(dp[i-1][k][j]+(mnm <= tim), dp[i][k][j]); } } } lg ans = 1e18; for(int i = 0; i <= n; i++) { for(int j = 0; j <= d; j++) { ans = min(ans, dp[n][i][j]); } } cout << ans << '\n'; }
#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...