Submission #996460

#TimeUsernameProblemLanguageResultExecution timeMemory
996460overwatch9Stove (JOI18_stove)C++17
20 / 100
1058 ms133804 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; int n, k; vector <int> t; const int maxn = 5000 + 1; ll dp[maxn][maxn]; bool ready[maxn][maxn]; ll solve(int i, int left) { if (i > n) return 0; if (left <= 0 && i <= n) return 1e18; if (ready[i][left]) return dp[i][left]; ll ans = 1e18; for (int j = i; j <= n; j++) ans = min(ans, solve(j+1, left - 1) + t[j] - t[i] + 1); ready[i][left] = true; dp[i][left] = ans; return ans; } int main() { cin >> n >> k; t.resize(n+1); for (int i = 1; i <= n; i++) cin >> t[i]; cout << solve(1, k) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...