AtCoder Beginner Contest 037

Submission #1024243

Source codeソースコード

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

def read_numbers; gets.split.map(&:to_i); end
H, W = read_numbers.map{|i| i+2}
M = 1000000007
MAP = 
  Array.new(W, 0) +
  (H-2).times.flat_map{ [0] + read_numbers + [0] } +
  Array.new(W, 0)
ANS = Array.new(W*H)
DIRS = [+1, -1, +W, -W]
 
$ans = 0
def calc(pos)
  ret = 1

  i = 0
  v = MAP[pos]
  while i < 4
    d = DIRS[i]
    if v < MAP[pos+d]
      plus = ANS[pos+d] || calc(pos+d)
      ret += plus
    end
    i += 1
  end

  ret %= M
  ANS[pos] = ret; $ans += ret
  return ret
end
 
(H-2).times do |y|
  (W-2).times do |x|
    pos = W+1 + y*W+x
    calc(pos) unless ANS[pos]
  end
end
 
p $ans % M

Submission

Task問題 D - 経路
User nameユーザ名 Yutaka Hara
Created time投稿日時
Language言語 Ruby (2.3.3)
Status状態 AC
Score得点 100
Source lengthソースコード長 763 Byte
File nameファイル名
Exec time実行時間 1251 ms
Memory usageメモリ使用量 168268 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 1142 ms 37056 KB
01.txt AC 1196 ms 168268 KB
02.txt AC 1093 ms 36160 KB
03.txt AC 50 ms 4168 KB
04.txt AC 50 ms 4172 KB
05.txt AC 50 ms 4168 KB
06.txt AC 51 ms 4292 KB
07.txt AC 51 ms 4296 KB
08.txt AC 50 ms 4168 KB
09.txt AC 50 ms 4164 KB
10.txt AC 54 ms 4416 KB
11.txt AC 1166 ms 36420 KB
12.txt AC 1179 ms 36360 KB
13.txt AC 1197 ms 36420 KB
14.txt AC 1176 ms 36420 KB
15.txt AC 1126 ms 36684 KB
16.txt AC 1251 ms 36312 KB
17.txt AC 1183 ms 36336 KB
18.txt AC 1032 ms 36288 KB
19.txt AC 988 ms 36292 KB
sample01.txt AC 50 ms 4164 KB
sample02.txt AC 50 ms 4164 KB