Submission #3601481

---

Source Code Expand

#!/usr/bin/python3
# -*- coding: utf-8 -*-

"""
https://beta.atcoder.jp/contests/abc008/tasks/abc008_2
"""

import sys
from inspect import currentframe
from itertools import permutations
import math

def debug(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=sys.stderr)


W, H = map(int, input().split())
N = int(input())
cranes = [list(map(int, input().split())) for _ in range(N)]

def get_gold_blocks(gold_blocks, crane):
    pointer = [crane[0] - 1, crane[1] - 1]
    gold_blocks[pointer[1]][pointer[0]] = False
    pointer[0] += 1
    while pointer[0] < W and gold_blocks[pointer[1]][pointer[0]]:
        gold_blocks[pointer[1]][pointer[0]] = False
        pointer[0] += 1

    pointer = [crane[0] - 1, crane[1] - 1]
    pointer[0] -= 1
    while pointer[0] >= 0 and gold_blocks[pointer[1]][pointer[0]]:
        gold_blocks[pointer[1]][pointer[0]] = False
        pointer[0] -= 1

    pointer = [crane[0] - 1, crane[1] - 1]
    pointer[1] += 1
    while pointer[1] < H and gold_blocks[pointer[1]][pointer[0]]:
        gold_blocks[pointer[1]][pointer[0]] = False
        pointer[1] += 1
        
    pointer = [crane[0] - 1, crane[1] - 1]
    pointer[1] -= 1
    while pointer[1] >= 0 and gold_blocks[pointer[1]][pointer[0]]:
        gold_blocks[pointer[1]][pointer[0]] = False
        pointer[1] -= 1

earned_list = []        
for crane_order in permutations(cranes):
    gold_blocks = [[True for _ in range(W)] for _ in range(H)]
    for crane in crane_order:
        get_gold_blocks(gold_blocks, crane)
    earned_list.append(sum([r.count(False) for r in gold_blocks]))
    
print(max(earned_list))

Submission Info

Judge Result