Submission #787262

#	Time	Username	Problem	Language	Result	Execution time	Memory
787262		YassirSalama	Stove (JOI18_stove)	C++14	50 / 100	298 ms	262144 KiB

stove

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#define dbg(x) cout << "[ " << #x << " ] : " << x<<endl;
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=5500;
int dp[MAXN][MAXN];//[i,k]
vector<int> v(MAXN,0);
int n,k;
vector<int> ds(MAXN,0);
const int INF=1e18;
int solve(int i,int kk){
	if(kk<0) return INF;
	if(i>=n-1) return 0;
	if(dp[i][kk]!=-1) return dp[i][kk];
	return dp[i][kk]=min(
			solve(i+1,kk-1),
			solve(i+1,kk)+ds[i]
		);
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n>>k;
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++) cin>>v[i];
for(int i=0;i<n;i++) ds[i]=v[i+1]-v[i]-1;
cout<<n+solve(0,k-1)<<endl;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50