Submission #1009535

#TimeUsernameProblemLanguageResultExecution timeMemory
1009535SG2AlokStove (JOI18_stove)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' #define hitaf ios_base::sync_with_stdio(false); cin.tie(NULL); #define fi first #define se second const ll MOD = 998244353; const ll INF = 1e18; ll n, k, a[100005]; int main(){ hitaf cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; vector<vector<ll>> dp(n + 2, vector<ll>(k + 2, -INF)); for(int i = 0; i <= k; i++) dp[0][i] = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= k; j++){ dp[i][j] = dp[i - 1][j]; if(j != 1) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i] - a[i - 1] - 1); } } cout << a[n] - dp[n][k] << endl; } /* 7 1 2 9 0 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...