Submission #1986180


Source Code Expand

Copy
lines = $stdin.read
array = lines.split("\n")
H,W   = array[0].split(" ").map(&:to_i)
A     = array[1..H+1].map{|s| s.split(" ").map(&:to_i)}

#require 'matrix'
#dp = Matrix.build(H,W){|row,col| 0}.to_a
dp = Array.new(H).map{Array.new(W){0}}

def rec(dp,i,j,sq,h,w)
  #puts "i=#{i},j=#{j},h=#{h},w=#{w}"
  if dp[i][j] == 0
    ans = 1
    if i > 0 and sq[i][j] < sq[i-1][j]
      ans += rec(dp,i-1,j,sq,h,w) # up
    end
    if i < h-1 and sq[i][j] < sq[i+1][j]
      ans += rec(dp,i+1,j,sq,h,w) # down
    end
    if j > 0 and sq[i][j] < sq[i][j-1]
      ans += rec(dp,i,j-1,sq,h,w) # left
    end
    if j < w-1 and sq[i][j] < sq[i][j+1]
      ans += rec(dp,i,j+1,sq,h,w) # right
    end
    ans
  else
    dp[i][j]
  end
end

for i in 0...H
  for j in 0...W
    dp[i][j] = rec(dp,i,j,A,H,W)
  end
end

puts dp.inject(&:+).inject(&:+)

Submission Info

Submission Time
Task D - 経路
User hiroyuking
Language Ruby (2.3.3)
Score 0
Code Size 873 Byte
Status TLE
Exec Time 2112 ms
Memory 167984 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 12
TLE × 12
Set Name Test Cases
sample sample01.txt, sample02.txt
All 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, sample01.txt, sample02.txt
Case Name Status Exec Time Memory
00.txt TLE 2109 ms 27260 KB
01.txt TLE 2109 ms 32892 KB
02.txt TLE 2109 ms 23036 KB
03.txt AC 7 ms 1788 KB
04.txt AC 7 ms 1788 KB
05.txt AC 7 ms 1788 KB
06.txt AC 8 ms 1788 KB
07.txt AC 9 ms 1788 KB
08.txt AC 8 ms 1788 KB
09.txt AC 7 ms 1788 KB
10.txt AC 15 ms 2428 KB
11.txt TLE 2110 ms 37372 KB
12.txt TLE 2110 ms 37500 KB
13.txt TLE 2110 ms 37372 KB
14.txt TLE 2109 ms 39420 KB
15.txt TLE 2109 ms 34684 KB
16.txt TLE 2110 ms 37500 KB
17.txt TLE 2110 ms 37372 KB
18.txt TLE 2111 ms 139328 KB
19.txt TLE 2112 ms 167984 KB
sample01.txt AC 7 ms 1788 KB
sample02.txt AC 7 ms 1788 KB