AtCoder Beginner Contest 037

Submission #882240

Source codeソースコード

if !ENV['RUBY_THREAD_VM_STACK_SIZE']
  exec({'RUBY_THREAD_VM_STACK_SIZE'=>'1000000000'}, '/usr/bin/ruby', $0)
else
  def get_path_count(y, x)
    count = 1
    value = $field[y][x]
 
    if value < $field[y][x-1]
      count += $cache[y][x-1] || get_path_count(y, x-1)
      count -= $mod if count >= $mod
    end
 
    if value < $field[y][x+1]
      count += $cache[y][x+1] || get_path_count(y, x+1)
      count -= $mod if count >= $mod
    end
 
    if value < $field[y-1][x]
      count += $cache[y-1][x] || get_path_count(y-1, x)
      count -= $mod if count >= $mod
    end
 
    if value < $field[y+1][x]
      count += $cache[y+1][x] || get_path_count(y+1, x)
      count -= $mod if count >= $mod
    end
 
    $cache[y][x] = count
  end
 
  $mod = 1000000007
  height, width = gets.split.map(&:to_i)
  $field = []
 
  $cache = Array.new(height+2).map{ Array.new(width+2) }
 
  $field << [0]*(width+2)
  height.times do
    $field << ("0 "+gets+" 0").split.map(&:to_i)
  end
  $field << [0]*(width+2)
 
  path_count = 0
 
  (1..height).each do |y|
    (1..width).each do |x|
      path_count += $cache[y][x] || get_path_count(y, x)
      path_count -= $mod if path_count>=$mod
    end
  end
 
  puts path_count
end

Submission

Task問題 D - 経路
User nameユーザ名 siman
Created time投稿日時
Language言語 Ruby (2.3.3)
Status状態 AC
Score得点 100
Source lengthソースコード長 1274 Byte
File nameファイル名
Exec time実行時間 1991 ms
Memory usageメモリ使用量 145856 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample01.txt,sample02.txt
All 100 / 100 00.txt,01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,sample01.txt,sample02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00.txt AC 1746 ms 22076 KB
01.txt AC 1991 ms 145856 KB
02.txt AC 1759 ms 21180 KB
03.txt AC 84 ms 4152 KB
04.txt AC 87 ms 4156 KB
05.txt AC 86 ms 4164 KB
06.txt AC 86 ms 4288 KB
07.txt AC 88 ms 4288 KB
08.txt AC 85 ms 4292 KB
09.txt AC 88 ms 4160 KB
10.txt AC 91 ms 4284 KB
11.txt AC 1895 ms 22208 KB
12.txt AC 1919 ms 21952 KB
13.txt AC 1914 ms 22328 KB
14.txt AC 1864 ms 21956 KB
15.txt AC 1812 ms 21696 KB
16.txt AC 1875 ms 22208 KB
17.txt AC 1911 ms 21948 KB
18.txt AC 1618 ms 20416 KB
19.txt AC 1416 ms 20416 KB
sample01.txt AC 84 ms 4164 KB
sample02.txt AC 85 ms 4156 KB