Submission #57315658

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
H, W, N = gets.split.map(&:to_i)
S = N.times.map{ gets.split.map(&:to_i) << _1 }
C = S.sort
x = []
y = []
prev = Array.new(N)
C.each do |r,c,i|
  j = x.bsearch_index{|x| x > c } || x.size
  x[j] = c
  y[j] = i
  prev[i] = y[j - 1] if j > 0
end
z = y[-1]
ans = []
rz, cz, _ = S[z]
ans << ('D' * (H - rz)) << ('R' * (W - cz))
until z.nil?
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

H, W, N = gets.split.map(&:to_i)
S = N.times.map{ gets.split.map(&:to_i) << _1 }
C = S.sort

x = []
y = []
prev = Array.new(N)
C.each do |r,c,i|
  j = x.bsearch_index{|x| x > c } || x.size
  x[j] = c
  y[j] = i
  prev[i] = y[j - 1] if j > 0
end

z = y[-1]

ans = []
rz, cz, _ = S[z]
ans << ('D' * (H - rz)) << ('R' * (W - cz))

until z.nil?
  rz, cz, _ = S[z]
  if w = prev[z]
    rw, cw, _ = S[w]
    ans << ('D' * (rz - rw)) << ('R' * (cz - cw))
  else
    ans << ('D' * (rz - 1)) << ('R' * (cz - 1))
  end
  z = prev[z]
end
puts x.size
puts ans.join.reverse

Submission Info

Judge Result