Uolevin kalansaalis

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 in_triangle(tri_y, tri_x, tri_size, tri_dir, cell_y, cell_x) # O(1)
  tri_y2 = tri_y + tri_size * tri_dir
  offset = ((((tri_y) % 2 == 1) && ((cell_y) % 2 == 0)) ? -1 : 0)

  if tri_dir == 1 
    dy = (tri_y - cell_y) / 2.0
    dyl = dy.ceil.to_i
    dyr = dy.floor.to_i

    return (tri_y <= cell_y && cell_y < tri_y2) && # dir = 1   
    (tri_x - offset) <= (cell_x + dyl) && # both
    (cell_x + offset) < (tri_x + (tri_size + dyr)) # both
  else    
    dy = (cell_y - tri_y) / 2.0
    dyl = dy.ceil.to_i
    dyr = dy.floor.to_i

    return (tri_y2 <= cell_y && cell_y <= tri_y) && # dir = -1
    (tri_x - offset) <= (cell_x + dyl) && # both
    (cell_x + offset) < (tri_x + (tri_size + dyr)) # both
  end

end

def in_triangle_slow(tri_y, tri_x, tri_size, tri_dir, cell_y, cell_x) # O(n)
  leftx = tri_x
  rightx = tri_x + tri_size - 1
  
  while leftx <= rightx
    if tri_y == cell_y && leftx <= cell_x && cell_x <= rightx
      return true
    end
    
    if tri_y % 2 == 0
      rightx -= 1
    else
      leftx += 1
    end
    
    tri_y += tri_dir
  end
  false
end

def get_value(y, x, size, dir, fishies)
  val = 0
  fishies.each do |fish|
    if in_triangle(y, x, size, dir, fish[0], fish[1])
      val += fish[2]
      #print("#{fish} is in tri")
    end
  end
  return val # total - val for true value 
end

height, width, count = gets.chomp.split(" ").map(&:to_i)
fishies = []
total = 0
min_size = (height <= 10 ? 1 : 10)

count.times do
  y, x, t = gets.chomp.split(" ")
  t = (t == "H" ? 1 : -10)
  fishies << [y.to_i-1, x.to_i-1, t]
  total += t
end

values = []
(0...height).each do |y|
  (0...width).each do |x|
    size = min_size
    dir = -1
    continue = true
    while continue
      legal = legal_triangle(y, x, size, dir, height, width)

=begin
      puts "--- legal=#{legal}, size=#{size}"
      (0...height).each do |y2|
        if y2 % 2 == 1
          print(" ")
        end
        (0...width).each do |x2|
          print(in_triangle(y, x, size, dir, y2, x2) ? "<>" : "..")
        end
        print("\n")
      end
=end

      if legal
        values << get_value(y, x, size, dir, fishies)
        size += 1
        #puts total - values[-1]
      else
        if dir == -1
          size = min_size
          dir = 1
        else
          continue = false
        end
      end
    end
  end
end

=begin
arr = []
height.times do 
  arr << []
  width.times do 
    arr[-1] << ".."
  end
end
fishies.each do |y, x, v|
  arr[y][x] = (v == 1 ? "HH" : "KK")
end

arr.each_with_index do |row, y2|
  if y2 % 2 == 1
    print(" ")
  end
    print(row.join)
  print("\n")
end
=end

puts(total - values.min)

# bruteforce, but
# 1. check in star pattern for fishies else no trisearch (optional)
# 2. make alg for triangle.legal?
# 3. make alg for x, y in triangle?

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 1, 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 1, 2

Verdict: ACCEPTED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 1, 2

Verdict: ACCEPTED

Test 14

Group: 1, 2

Verdict: ACCEPTED

Test 15

Group: 1, 2

Verdict: ACCEPTED

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