Submission #333297

#	Time	Username	Problem	Language	Result	Execution time	Memory
333297		AmineTrabelsi	Rabbit Carrot (LMIO19_triusis)	C++14	14 / 100	1086 ms	78644 KiB

triusis

#include "bits/stdc++.h"
using namespace std;
// Hi ☻
int n,m; // towerscnt, mxjump
vector<int> heights;
const int M = 5005;
map<int,int> dp[M];
int solve(int index,int prev){
    if(index >= n)return 0;
    auto it = dp[index].find(prev);
    if(it != dp[index].end())return it->second;
    if(heights[index]-prev > m){ // you need to lower this
        return dp[index][prev] = solve(index+1, prev+m)+1;
    }// you can get here
    // change this or don't 
    return dp[index][prev] = min(solve(index+1,heights[index]),solve(index+1,prev+m)+1); // change this to max possible
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    heights.assign(n,0);
    for(auto &i:heights)cin>>i;
    cout<<solve(0,0) <<'\n'; // rabbit start at 0 height 
    return 0;
}

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