제출 #871419

#제출 시각아이디문제언어결과실행 시간메모리
871419Cyber_WolfThe short shank; Redemption (BOI21_prison)C++17
0 / 100
23 ms125788 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 = 4e3+5; lg n, d, tim; lg dp[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][d] = 0; 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[i]+i-k); dp[i][j] = min(dp[i-1][j]+(mnm <= tim), dp[i-1][j+1]+(t[i] <= tim)); } // cout << dp[i][j] << ' '; } // cout << '\n'; } lg ans = 1e18; for(int i = 0; i <= d; i++) ans = min(ans, dp[n][i]); 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...