Codeforces Round #286 (Div. 1 A / Div. 2 C) - Mr. Kitayuta, the Treasure Hunter

Problem Statement:
506A - Mr. Kitayuta, the Treasure Hunter

Solution:
This is a standard dynamic programming problem, with a non-standard twist!

Firstly, let's forget about the constraints, define M(i, len) be the maximum number of gems can be collected if we start from island i after making a jump of length len. This is simply M(i, len) = max of  {M(i+len-1, len-1), M(i+len, len), M(i+len+1, len+1)} + [whether there is a gem in island i or not]. But we have a problem: Doing this will take \(O(N^2)\) where \(N \leq 30000\), which will not going to cut it in 1 second time constraint.



So the main observation is to realize that we don't require that much states after all, since in the worst case, len can only range from [1 .. 300], so there are less than 600 possible values for len in any case, reducing the runtime complexity to \(O(NM)\) where \(M < 600\).

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <utility>
#include <string>
using namespace std;

int dp[603][30003];
int mark[30003];
int N, D;
int Z = 299;
int main(){
    int u;
    scanf("%d %d",&N,&D);
    for(int i=0;i<N;++i){
        scanf("%d",&u);
        mark[u]++;
    }
    for(int i=30000;i>=0;--i){
        for(int k=0;k<=600;++k){
            dp[k][i] = mark[i];
            int cur = D+k-Z;
            if(cur<1)continue;
            if(i+cur<=30000){
                dp[k][i] = max(dp[k][i],dp[k][i+cur]+mark[i]);
            }
            if(i+cur+1<=30000 && k!=600){
                dp[k][i] = max(dp[k][i],dp[k+1][i+cur+1]+mark[i]);
            }
            if(i+cur-1<=30000 && cur != 1){
                dp[k][i] = max(dp[k][i],dp[k-1][i+cur-1]+mark[i]);
            }
        }
    }
    printf("%d\n",dp[Z][D]);
    return 0;
}