Submission #7087953
Source Code Expand
import sys import math import collections import itertools # Set max recursion limit sys.setrecursionlimit(1000000) w, h = map(int, input().split()) n = int(input()) xy_list = [] for i in range(n): x, y = map(int, input().split()) xy_list += [(x - 1, y - 1)] memo = [[[[-1] * (h + 1) for i in range(h + 1)] for j in range(w + 1)] for k in range(w + 1)] def recur(left, right, lower, upper, machine_list): if machine_list: machine_list = [(x, y) for x, y in machine_list if left <= x < right and lower <= y < upper] if not machine_list: return 0 ans = 0 for x, y in machine_list: ret = (right - left) + (upper - lower) - 1 for ((n_left, n_right), (n_lower, n_upper)) in list(product(((left, x), (x + 1, right)), ((lower, y), (y + 1, upper)))): if memo[n_left][n_right][n_lower][n_upper] != -1: ret += memo[n_left][n_right][n_lower][n_upper] else: ret += recur(n_left, n_right, n_lower, n_upper, machine_list) ans = max(ans, ret) memo[left][right][lower][upper] = ans return ans print(recur(0, w, 0, h, xy_list))
Submission Info
Submission Time | |
---|---|
Task | D - 金塊ゲーム |
User | ryuhei_py |
Language | PyPy3 (2.4.0) |
Score | 0 |
Code Size | 1203 Byte |
Status | RE |
Exec Time | 4437 ms |
Memory | 404488 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 80 | 0 / 19 | 0 / 1 | ||||||||||
Status |
|
|
|
|
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 | RE | 166 ms | 38640 KB |
sample_02.txt | RE | 163 ms | 38256 KB |
sample_03.txt | RE | 173 ms | 39408 KB |
subtask1_01.txt | RE | 162 ms | 38256 KB |
subtask1_02.txt | RE | 166 ms | 38896 KB |
subtask1_03.txt | RE | 162 ms | 38256 KB |
subtask1_04.txt | RE | 171 ms | 40048 KB |
subtask1_05.txt | RE | 214 ms | 68828 KB |
subtask1_06.txt | RE | 161 ms | 38256 KB |
subtask1_07.txt | RE | 174 ms | 42608 KB |
subtask1_08.txt | RE | 162 ms | 38256 KB |
subtask1_09.txt | RE | 695 ms | 404488 KB |
subtask1_10.txt | RE | 687 ms | 404232 KB |
subtask1_11.txt | RE | 688 ms | 404232 KB |
subtask1_12.txt | RE | 162 ms | 38384 KB |
subtask1_13.txt | RE | 187 ms | 48092 KB |
subtask1_14.txt | RE | 686 ms | 404360 KB |
subtask1_15.txt | RE | 685 ms | 404232 KB |
subtask1_16.txt | RE | 171 ms | 41584 KB |
subtask1_17.txt | RE | 183 ms | 46960 KB |
subtask1_18.txt | RE | 164 ms | 38640 KB |
subtask1_19.txt | RE | 161 ms | 38256 KB |
subtask1_20.txt | RE | 162 ms | 38256 KB |
subtask1_21.txt | RE | 203 ms | 68316 KB |
subtask1_22.txt | RE | 202 ms | 75100 KB |
subtask1_23.txt | RE | 164 ms | 38896 KB |
subtask1_24.txt | RE | 525 ms | 303624 KB |
subtask1_25.txt | RE | 688 ms | 404232 KB |
subtask2_01.txt | RE | 170 ms | 40688 KB |
subtask2_02.txt | RE | 168 ms | 40816 KB |
subtask2_03.txt | RE | 200 ms | 70108 KB |
subtask2_04.txt | RE | 683 ms | 404232 KB |
subtask2_05.txt | RE | 373 ms | 192092 KB |
subtask2_06.txt | RE | 229 ms | 99420 KB |
subtask2_07.txt | RE | 192 ms | 55644 KB |
subtask2_08.txt | RE | 192 ms | 54748 KB |
subtask2_09.txt | RE | 305 ms | 169052 KB |
subtask2_10.txt | RE | 659 ms | 376456 KB |
subtask2_11.txt | RE | 206 ms | 69596 KB |
subtask2_12.txt | RE | 662 ms | 372104 KB |
subtask2_13.txt | RE | 686 ms | 404232 KB |
subtask2_14.txt | RE | 687 ms | 404232 KB |
subtask2_15.txt | RE | 690 ms | 404232 KB |
subtask2_16.txt | RE | 203 ms | 68316 KB |
subtask2_17.txt | RE | 204 ms | 68316 KB |
subtask2_18.txt | RE | 400 ms | 195592 KB |
subtask2_19.txt | RE | 316 ms | 150364 KB |
subtask2_20.txt | RE | 315 ms | 168540 KB |
subtask2_21.txt | RE | 321 ms | 168540 KB |
subtask2_22.txt | RE | 488 ms | 257800 KB |
subtask2_23.txt | RE | 485 ms | 257800 KB |
subtask2_24.txt | RE | 690 ms | 404232 KB |
subtask2_25.txt | RE | 689 ms | 404232 KB |
subtask3_01.txt | RE | 3238 ms | -617612 KB |
subtask3_02.txt | RE | 2543 ms | -616756 KB |
subtask3_03.txt | RE | 2397 ms | -616600 KB |
subtask3_04.txt | TLE | 4437 ms | -616172 KB |
subtask3_05.txt | TLE | 4431 ms | -616200 KB |
subtask3_06.txt | RE | 2483 ms | -616252 KB |
subtask3_07.txt | RE | 2472 ms | -616380 KB |
subtask3_08.txt | TLE | 4364 ms | -1777144 KB |
subtask3_09.txt | RE | 3468 ms | -616292 KB |
subtask3_10.txt | RE | 2152 ms | -616384 KB |
subtask3_11.txt | RE | 2691 ms | -616224 KB |
subtask3_12.txt | RE | 2904 ms | -616560 KB |
subtask3_13.txt | RE | 1953 ms | -616208 KB |
subtask3_14.txt | TLE | 4357 ms | -1785080 KB |
subtask3_15.txt | RE | 2072 ms | -616420 KB |
subtask3_16.txt | TLE | 4361 ms | -1728248 KB |
subtask3_17.txt | RE | 2243 ms | -616424 KB |
subtask3_18.txt | RE | 2294 ms | -616376 KB |
subtask3_19.txt | RE | 2559 ms | -616324 KB |
subtask3_20.txt | RE | 2500 ms | -616496 KB |
subtask3_21.txt | RE | 2549 ms | -616212 KB |
subtask3_22.txt | RE | 2265 ms | -616356 KB |
subtask3_23.txt | RE | 2521 ms | -616292 KB |
subtask3_24.txt | RE | 2510 ms | -616456 KB |
subtask3_25.txt | RE | 2910 ms | -616256 KB |