Super Mario GEMA

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//x - número de moedas p/ voar
//n - nro de moedas da fase
//d - distância que voa
const int N = 4000;
ll in[N][2];
int dp[N][N];
int n,x;
ll d;

int next(int i){
    int lo = i, hi = n-1;
    while (hi != lo){
        int mi = (hi + lo + 1)/2;
        ll dist = in[mi][0] - in[i][0];
        if (dist <= d){
            lo = mi;
        }else{
            hi = mi - 1;
        }
    }
    return lo;
}

int f(int c,int k){
//res -> o valor retornado pela função
//k -> nro de moedas que já pegou p/ voar
//c -> nro de moedas pegas no round
    if (c==n){ //chegou no final.
        return 0;
    }
    int& res = dp[c][k];
    if (res != -1){
        res = f(c+1, k); //chama a prox moeda
    }
    if(in[c][1]){
        if(k != x-1) { //ele vai voar? sim / não
            res = max(res , 1 + f(c+1,k+1)); //se voar
        }else{
            int w = next(c);
            res = (w - c + 1) + f(w + 1, 0);
        }

    }
    return res;
}


int main(){
    memset (dp, -1, sizeof dp);
    scanf("%d %d %d", &n, &x, &d);
    for (int i=0;i<n;i++){
        scanf("%lld %lld", &in[i][0], &in[i][1]);
    }
    printf("%d\n", f(0,0));
    return 0;
}