Submission #637944

#	Time	Username	Problem	Language	Result	Execution time	Memory
637944		Iwanttobreakfree	Rabbit Carrot (LMIO19_triusis)	C++17	14 / 100	1 ms	348 KiB

triusis

#include <iostream>
#include <vector>
using namespace std;
int best=1e9;
vector<vector<int>> dp(100,vector<int> (100,-1));
int DP(int i,int h,vector<int>& v,int m){
    if(i<0)return 1e9;
    if(dp[i][h]!=-1)return dp[i][h];
    dp[i][h]=1e9;
    for(int j=max(0,h-m);j<100;j++){
        dp[i][h]=min(dp[i][h],DP(i-1,j,v,m)+(j!=v[i-1]));
    }
    return dp[i][h];
}
int main(){
    int n,m,ans=1e9;
    cin>>n>>m;
    vector<int> v(n+1);
	dp[0][0]=0;
    for(int i=1;i<=n;i++)cin>>v[i];
    for(int i=0;i<100;i++){
        ans=min(ans,DP(n,i,v,m)+(i!=v[n]));
    }
    cout<<ans<<'\n';
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37