제출 #638915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638915		rc_catunta	Stove (JOI18_stove)	C++14	50 / 100	112 ms	99800 KiB

stove

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int INF = 1000000010;
int memo[5001][5001];
vi guests;
int N,K,x;

int dp(int g,int m){
    // Casos Base
    if(m>K) return INF;
    if(g==N-1) return 1;
    // Memoizacion
    if(memo[g][m]!=-1) return memo[g][m];
    // Busqueda
    int res = min(1+dp(g+1,m+1),guests[g+1]-guests[g]+dp(g+1,m));
    return memo[g][m]=res;
}

int main(){
    ios_base::sync_with_stdio(false);
    memset(memo,-1,sizeof(memo));
    cin>>N>>K;
    for(int i=0;i<N;i++){
        cin>>x;
        guests.push_back(x);
    }
    cout<<dp(0,1)<<"\n";
    return 0;
}

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