C問題で限界。難しい。
気づき
- r（全体のマス）が小さい
<
より有名人は同じ時間に登場しない＆単調増加。少なくとも1分離れている。
まず、典型的なDPで答えを求めることができる。
DPテーブルを、dp[i]をi番目までみたときの、写真を取れる有名人の数の最大値、として
遷移は、dp[i]は移動が間に合う場所dp[j]の値+1とのmax（dp[i]=max(dp[i],dp[j] ただしjはdp[i]に間に合う場所)）で解ける。
が、なので改善が必要。
ここで、i番目より前を毎回全部みていたら間に合わないので、i番目より前でi番目に間に合う最大値を高速に求めたい。
そこでrが小さい（街が小さいこと）を活用する。
実は、分あれば、
の街の端から端まで移動することができる。つまり、任意の座標から任意の座標に移動できる。
よって、dp[i]を更新するときは分以上の移動時間が確保できるマスからは、常にdp[i]へ移動できる。
ある座標にいるときの時間は固定かつ単調増加かつ重複がないので、「dp[0]からdp[i-r*2]」の範囲は、確実に分以上の移動時間を取ることができる。
よって「dp[0]からdp[i-r*2]」の最大値をもっておけば、DP遷移時にみる範囲を減らすことができる。（dp[i]を更新すれば、その後dp[i]が更新されることはないので、別の配列で累積maxをとっておけばよい）
この方法でAC。
