Uolevin kalansaalis

# when make fish, make reverse triangle
# 2dim arr<hash> 
# get max

def legal_triangle(y, x, size, dir, height, width) # dir = -1 or 1 # O(1)
  return x >= 0 &&
        (x + size) <= (width) && 
        (y + (dir * size) + 1) >= 0 &&
        (y + (dir * size)) <= height
end

def triangle(tri_y, tri_x, tri_size, tri_dir) # O(n) # returns only leftmost from each row
  leftx = tri_x - tri_size + 1
  rightx = tri_x
  values = []

  while leftx <= rightx
    
    values << [tri_y, leftx, rightx - leftx + 1] #(leftx..rightx).to_a
    
    if tri_y % 2 == 0
      rightx -= 1
    else
      leftx += 1
    end
    
    tri_y += tri_dir
  end

  return values
end

height, width, count = gets.chomp.split(" ").map(&:to_i)

board = []
height.times do
  board << []
end

#puts board.to_s

total = 0

count.times do
  y, x, type = gets.chomp.split(" ")
  x = x.to_i - 1
  y = y.to_i - 1
  type = (type == "H" ? 1 : -10)
  total += type
  size = 1
  legal1 = true
  legal2 = true
  while legal1 || legal2
    legal1 = legal_triangle(y, x - size + 1, size,  1, height, width)
    legal2 = legal_triangle(y, x - size + 1, size, -1, height, width)
    
    if legal1
      values = triangle(y, x, size, 1)
      values.each do |celly, cellx, len|
        board[celly] << [cellx, len, size, type]
      end
    end

    if legal2
      values = triangle(y, x, size, -1)
      values.each do |celly, cellx, len|
        board[celly] << [cellx, len, size, type]
      end
    end

    size += 1
  end
end

maxes = []
board.each do |row|
  ends = []
  #ind = 0
  count = 0
  mincount = 99999999999
  row.sort_by{ |a, b, c| a }.each do |x, len, size, type|
    #ind = x
    ends << [x - len + 1, type]
    count += type
    while ends.length > 0 && ends[0][0] <= x
      _, type = ends.shift
      count -= type[1]
    end
    if count < mincount
      mincount = count
    end
  end
  maxes << mincount
end

puts total - maxes.min

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 1, 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 1, 2

Verdict: WRONG ANSWER

Test 5

Group: 1, 2

Verdict: WRONG ANSWER

Test 6

Group: 1, 2

Verdict: WRONG ANSWER

Test 7

Group: 1, 2

Verdict: WRONG ANSWER

Test 8

Group: 1, 2

Verdict: WRONG ANSWER

Test 9

Group: 1, 2

Verdict: WRONG ANSWER

Test 10

Group: 1, 2

Verdict: WRONG ANSWER

Test 11

Group: 1, 2

Verdict: ACCEPTED

Test 12

Group: 1, 2

Verdict: WRONG ANSWER

Test 13

Group: 1, 2

Verdict: WRONG ANSWER

Test 14

Group: 1, 2

Verdict: WRONG ANSWER

Test 15

Group: 1, 2

Verdict: WRONG ANSWER

Test 16

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 2

Verdict: TIME LIMIT EXCEEDED