Submission #1071259

---

Source Code Expand

if !ENV['RUBY_THREAD_VM_STACK_SIZE']
  exec({'RUBY_THREAD_VM_STACK_SIZE'=>'1000000000'}, '/usr/bin/ruby', $0)
end

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
  a = As[k]
  t = k + W + 2; ret += dp(t) if As[t] > a
  t = k - W - 2; ret += dp(t) if As[t] > a
  t = k + 1; ret += dp(t) if As[t] > a
  t = k - 1; ret += dp(t) if As[t] > a
  @dp[k] = ret
end

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

Submission Info

Judge Result