505C - Mr Kitayuta the Treasure Hunter - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define dd double
#define ll long long int 
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define pr pair<ll,ll>
#define pri pair<pr,ll>
#define pir pair<ll,pr>
#define ppr pair<pr,pr>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll INF=9e15;
ll mod=998244353;
ll solve(vector<ll> &v1,ll in1,ll curr,ll lower,vector<vector<ll> > &dp){
   if(in1>=v1.size()) return 0;
   ll val=curr-lower;
   if(dp[in1][val]!=-1) return dp[in1][val];
   ll ans1=0;
   if(curr>1) ans1=solve(v1,in1+curr-1,curr-1,lower,dp);
   ans1=max(ans1,solve(v1,in1+curr,curr,lower,dp));
   ans1=max(ans1,solve(v1,in1+curr+1,curr+1,lower,dp));
   dp[in1][val]=ans1+v1[in1];
   return dp[in1][val];
}
int main(){
   #ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
   freopen("opt.txt","w",stdout);
   #endif
   fastio;
   ll te=1;
   // cin>>te;
   while(te--){
     vector<ll> v1(30001);
     ll n,d,i,j,t;
     cin>>n>>d;
     for(i=0;i<n;i++){
      cin>>j;
      v1[j]++;
     }
     ll lower=d-245;
     vector<vector<ll> > dp(30001,vector<ll>(500,-1));
     cout<<v1[0]+solve(v1,d,d,lower,dp)<<endl;
   }
}