Submission #1009522

#TimeUsernameProblemLanguageResultExecution timeMemory
1009522altern23Stove (JOI18_stove)C++17
20 / 100
17 ms68956 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define pii pair<ll,ll> #define fi first #define sec second const ll MOD = 1e9 + 7; const ll N = 5e3 + 5; const ll INF = 1e18; ll dp[N][N]; int32_t main(){ cin.tie(0)->sync_with_stdio(0); int tc = 1; // cin >> tc; while(tc--){ ll n,k; cin >> n >> k; vector<ll>vec(n+5); for(int i=1;i<=n;i++) cin >> vec[i]; for(int i=1;i<=n;i++){ for(int j=0;j<=k;j++){ dp[i][j] = -INF; } } dp[0][0] = 0; for(int i=1;i<=n;i++){ for(int j=0;j<k;j++){ dp[i][j] = dp[i-1][j]; if(j) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + (vec[i] - vec[i-1] - 1)); } } cout << vec[n] - vec[1] + 1 - dp[n][k-1] << endl; } } /* 1 2 3 4 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...