Submission #3451564


Source Code Expand

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: 1つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる,始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    global dp

    N = int(input())
    B = [li_input() for _ in range(N)]

    B.sort(key=lambda b:b[1], reverse=True)
    B.sort(key=lambda b:b[0], reverse=True)
    # print(B)

    dp = [1] * N
    
    bi = 1
    pw, ph = B[0][0], B[0][1]
    while bi < N:
        w, h = B[bi]

        if w < pw and h < ph:
            pw, ph = w,h
            dp[bi] += dp[bi-1]
        else:
            dp[bi] = dp[bi-1]
        
        bi += 1

    # print(dp)

    print(dp[-1])


main()

Submission Info

Submission Time
Task D - プレゼント
User Szarny
Language Python (3.4.3)
Score 0
Code Size 3654 Byte
Status WA
Exec Time 513 ms
Memory 26620 KB

Judge Result

Set Name Sample Subtask0 All
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 4
AC × 6
WA × 13
AC × 8
WA × 26
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask0 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt
All sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt AC 55 ms 5140 KB
sample1.txt AC 35 ms 4672 KB
sample2.txt AC 35 ms 4756 KB
sample3.txt AC 35 ms 4672 KB
subtask0_0.txt WA 37 ms 4756 KB
subtask0_1.txt WA 35 ms 4756 KB
subtask0_10.txt AC 39 ms 4756 KB
subtask0_11.txt AC 38 ms 4756 KB
subtask0_12.txt WA 39 ms 4756 KB
subtask0_13.txt WA 39 ms 4756 KB
subtask0_14.txt WA 39 ms 4756 KB
subtask0_2.txt WA 36 ms 4672 KB
subtask0_3.txt WA 36 ms 4756 KB
subtask0_4.txt WA 38 ms 4756 KB
subtask0_5.txt WA 36 ms 4756 KB
subtask0_6.txt WA 39 ms 4756 KB
subtask0_7.txt WA 39 ms 4756 KB
subtask0_8.txt WA 39 ms 4756 KB
subtask0_9.txt WA 38 ms 4756 KB
subtask1_0.txt WA 298 ms 16772 KB
subtask1_1.txt WA 42 ms 5004 KB
subtask1_10.txt AC 375 ms 26620 KB
subtask1_11.txt AC 369 ms 23564 KB
subtask1_12.txt WA 497 ms 24344 KB
subtask1_13.txt WA 490 ms 24336 KB
subtask1_14.txt WA 504 ms 24424 KB
subtask1_2.txt WA 103 ms 7896 KB
subtask1_3.txt WA 415 ms 21348 KB
subtask1_4.txt WA 513 ms 24208 KB
subtask1_5.txt WA 95 ms 7420 KB
subtask1_6.txt WA 358 ms 19220 KB
subtask1_7.txt WA 202 ms 12548 KB
subtask1_8.txt WA 421 ms 21712 KB
subtask1_9.txt WA 221 ms 13316 KB