Submission #3602120


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
import numpy as np
from collections import namedtuple

sys.setrecursionlimit(100000)

def debug_print(*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())
Point = namedtuple('Point', ['x', 'y'])
Area = namedtuple('Area', ['bottom_left', 'top_right'])
cranes = [Point(*map(int, input().split())) for _ in range(N)]
earn_memo = {}

def is_in_area(area, point):
    return area.bottom_left.x <= point.x < area.top_right.x and area.bottom_left.y <= point.y < area.top_right.y

import bisect
def in_area_points(area, sorted_points):
    min_x = bisect.bisect_left(sorted_points, area.bottom_left)
    max_x = bisect.bisect_right(sorted_points, area.top_right)
    in_x = sorted_points[min_x: max_x]
    return [point for point in in_x if area.bottom_left.y <= point.y < area.top_right.y]

# areaで表わされる座標をpoint=(x,y)で4分割したareaを計算
# 但し、座標がareaに入っていなければ空、端なら1-2の領域となる
def split4(area, point):
    bl = area.bottom_left
    tr = area.top_right
    areas = [Area(Point(bl.x, bl.y), Point(point.x, point.y)),
             Area(Point(bl.x, point.y + 1), Point(point.x, tr.y)),
             Area(Point(point.x + 1, bl.y), Point(tr.x, point.y)),
             Area(Point(point.x + 1, point.y + 1), Point(tr.x, tr.y))]
    return list(filter(lambda a: a.bottom_left.x < a.top_right.x and a.bottom_left.y < a.top_right.y, areas))

def earn_gold(area, cranes):
    if area in earn_memo.keys():
        return earn_memo[area]
    earns = [0]
    #in_cranes = [crane for crane in cranes if is_in_area(area, crane)]
    in_cranes = in_area_points(area, cranes)
    # debug_print(area)
    # debug_print(in_cranes)
    # debug_print(in_cranes2)
    for crane in in_cranes:
        sub_areas = split4(area, crane)
        earn_this_split = (area.top_right.y - area.bottom_left.y) + (area.top_right.x - area.bottom_left.x) - 1
        earns.append(sum([earn_gold(sub_area, in_cranes) for sub_area in sub_areas]) + earn_this_split)
    earn = max(earns)
    earn_memo[area] = earn
    return earn

# import cProfile
# cranes.sort()
# cProfile.run('earn_gold(Area(Point(1,1), Point(W + 1, H + 1)), cranes)')


print(earn_gold(Area(Point(1,1), Point(W + 1, H + 1)), cranes))

Submission Info

Submission Time
Task D - 金塊ゲーム
User terakoji
Language Python (3.4.3)
Score 0
Code Size 2680 Byte
Status WA
Exec Time 538 ms
Memory 23396 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 80 0 / 19 0 / 1
Status
AC × 2
WA × 1
AC × 5
WA × 20
AC × 5
WA × 45
AC × 5
WA × 70
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt
Subtask2 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt, subtask3_15.txt, subtask3_16.txt, subtask3_17.txt, subtask3_18.txt, subtask3_19.txt, subtask3_20.txt, subtask3_21.txt, subtask3_22.txt, subtask3_23.txt, subtask3_24.txt, subtask3_25.txt
Case Name Status Exec Time Memory
sample_01.txt AC 371 ms 23396 KB
sample_02.txt AC 167 ms 13296 KB
sample_03.txt WA 178 ms 13296 KB
subtask1_01.txt AC 171 ms 13296 KB
subtask1_02.txt WA 171 ms 13296 KB
subtask1_03.txt WA 172 ms 13296 KB
subtask1_04.txt WA 172 ms 13296 KB
subtask1_05.txt AC 168 ms 13296 KB
subtask1_06.txt AC 170 ms 13296 KB
subtask1_07.txt WA 173 ms 13296 KB
subtask1_08.txt AC 168 ms 13300 KB
subtask1_09.txt WA 170 ms 13296 KB
subtask1_10.txt WA 171 ms 13296 KB
subtask1_11.txt WA 172 ms 13296 KB
subtask1_12.txt WA 172 ms 13188 KB
subtask1_13.txt WA 171 ms 13296 KB
subtask1_14.txt WA 174 ms 13296 KB
subtask1_15.txt WA 177 ms 13296 KB
subtask1_16.txt WA 175 ms 13296 KB
subtask1_17.txt WA 175 ms 13296 KB
subtask1_18.txt AC 173 ms 13296 KB
subtask1_19.txt WA 170 ms 13296 KB
subtask1_20.txt WA 172 ms 13296 KB
subtask1_21.txt WA 173 ms 13296 KB
subtask1_22.txt WA 176 ms 13296 KB
subtask1_23.txt WA 176 ms 13296 KB
subtask1_24.txt WA 175 ms 13296 KB
subtask1_25.txt WA 176 ms 13296 KB
subtask2_01.txt WA 196 ms 13424 KB
subtask2_02.txt WA 195 ms 13424 KB
subtask2_03.txt WA 238 ms 13848 KB
subtask2_04.txt WA 220 ms 13860 KB
subtask2_05.txt WA 293 ms 14480 KB
subtask2_06.txt WA 297 ms 14600 KB
subtask2_07.txt WA 305 ms 14544 KB
subtask2_08.txt WA 382 ms 15068 KB
subtask2_09.txt WA 421 ms 15804 KB
subtask2_10.txt WA 417 ms 15804 KB
subtask2_11.txt WA 428 ms 15688 KB
subtask2_12.txt WA 362 ms 15472 KB
subtask2_13.txt WA 317 ms 15068 KB
subtask2_14.txt WA 265 ms 14448 KB
subtask2_15.txt WA 178 ms 13296 KB
subtask2_16.txt WA 262 ms 14316 KB
subtask2_17.txt WA 442 ms 15796 KB
subtask2_18.txt WA 422 ms 15744 KB
subtask2_19.txt WA 402 ms 15624 KB
subtask2_20.txt WA 469 ms 15988 KB
subtask2_21.txt WA 526 ms 16052 KB
subtask2_22.txt WA 338 ms 15320 KB
subtask2_23.txt WA 373 ms 15580 KB
subtask2_24.txt WA 369 ms 15552 KB
subtask2_25.txt WA 457 ms 16036 KB
subtask3_01.txt WA 169 ms 13296 KB
subtask3_02.txt WA 192 ms 13548 KB
subtask3_03.txt WA 199 ms 13520 KB
subtask3_04.txt WA 213 ms 13788 KB
subtask3_05.txt WA 267 ms 14380 KB
subtask3_06.txt WA 224 ms 13932 KB
subtask3_07.txt WA 213 ms 13868 KB
subtask3_08.txt WA 312 ms 14692 KB
subtask3_09.txt WA 299 ms 14816 KB
subtask3_10.txt WA 434 ms 16240 KB
subtask3_11.txt WA 291 ms 15328 KB
subtask3_12.txt WA 464 ms 16268 KB
subtask3_13.txt WA 489 ms 16540 KB
subtask3_14.txt WA 379 ms 15780 KB
subtask3_15.txt WA 482 ms 16324 KB
subtask3_16.txt WA 428 ms 16072 KB
subtask3_17.txt WA 465 ms 16432 KB
subtask3_18.txt WA 279 ms 14528 KB
subtask3_19.txt WA 351 ms 15916 KB
subtask3_20.txt WA 259 ms 14536 KB
subtask3_21.txt WA 538 ms 16676 KB
subtask3_22.txt WA 441 ms 16464 KB
subtask3_23.txt WA 490 ms 16508 KB
subtask3_24.txt WA 501 ms 16428 KB
subtask3_25.txt WA 469 ms 16332 KB