Submission #1071250

---

Source Code Expand

H, W = gets.split.map(&:to_i)
As = ([[0] * (W + 2)] + readlines.map{|l| [0] + l.split.map(&:to_i) + [0]} + [[0] * (W + 2)]).flatten
MOD = 1_000_000_007

def dp(k)
  return @dp[k] if @dp[k]
  ret = 1
  ret += dp(k + W + 2) if As[k + W + 2] > As[k]
  ret += dp(k - W - 2) if As[k - W - 2] > As[k]
  ret += dp(k + 1) if As[k + 1] > As[k]
  ret += dp(k - 1) if As[k - 1] > As[k]
  @dp[k] = ret
end

@dp = Array.new((H + 2) * (W + 2), nil)
ans = 0
(1 .. H).each do |i|
  (1 .. W).each do |j|
    ans = (ans + dp(i * (W + 2) + j + 1)) % MOD
  end
end
puts ans

Submission Info

Judge Result