Submission #16130159


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(A):
    A = A - 1
    N = len(A) // 3
    A = np.append(A, (N, N))
    INF = 1 << 30
    dp = np.full((N + 1, N + 1), -INF, np.int64)
    a, b = A[:2]
    dp[a, b] = dp[b, a] = 0
    dp_max = np.full(N + 1, -INF, np.int64)
    dp_max[a] = dp_max[b] = 0
    add = 0
    update = np.empty((100 * N, 3), np.int64)
    for n in range(N):
        a, b, c = A[3 * n + 2:3 * n + 5]
        if a == b == c:
            add += 1
            continue
        p = 0
        # 色を持ちかえるだけの遷移
        for _ in range(3):
            a, b, c = b, c, a
            update[p], p = (a, b, dp_max.max()), p + 1
            for k in range(N):
                update[p], p = (k, a, dp_max[k]), p + 1

        for _ in range(3):
            a, b, c = b, c, a
            # 色 a をそろえる遷移
            if a == b:
                for k in range(N):
                    # もともと a, k をもっている
                    update[p], p = (c, k, dp[a, k] + 1), p + 1
            # もともと a, a, をもっている
            update[p], p = (b, c, dp[a, a] + 1), p + 1
        for i in range(p):
            a, b, x = update[i]
            dp[a, b] = dp[b, a] = max(dp[a, b], x)
            dp_max[a] = max(dp_max[a], x)
            dp_max[b] = max(dp_max[b], x)
    return dp_max.max() + add

A = np.array(read().split(), np.int64)[1:]

print(main(A))

Submission Info

Submission Time
Task F - Brave CHAIN
User maspy
Language Python (3.8.2)
Score 600
Code Size 1651 Byte
Status
Exec Time 829 ms
Memory 138876 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
× 3
× 55
Set Name Test Cases
Sample sample00, sample01, sample02
All case03, case04, case05, case06, case07, case08, case09, case10, case11, case12, case13, case14, case15, case16, case17, case18, case19, case20, case21, case22, case23, case24, case25, case26, case27, case28, case29, case30, case31, case32, case33, case34, case35, case36, case37, case38, case39, case40, case41, case42, case43, case44, case45, case46, case47, case48, case49, case50, case51, case52, case53, case54, sample00, sample01, sample02
Case Name Status Exec Time Memory
case03 818 ms 138108 KB
case04 804 ms 138284 KB
case05 813 ms 138760 KB
case06 829 ms 138108 KB
case07 804 ms 138120 KB
case08 798 ms 137692 KB
case09 542 ms 118224 KB
case10 731 ms 132928 KB
case11 480 ms 106500 KB
case12 490 ms 107232 KB
case13 489 ms 107232 KB
case14 492 ms 106620 KB
case15 487 ms 106564 KB
case16 737 ms 137700 KB
case17 683 ms 134340 KB
case18 538 ms 117200 KB
case19 702 ms 138448 KB
case20 511 ms 110280 KB
case21 488 ms 107560 KB
case22 512 ms 111552 KB
case23 486 ms 107556 KB
case24 519 ms 118464 KB
case25 574 ms 131056 KB
case26 690 ms 137928 KB
case27 676 ms 138248 KB
case28 562 ms 122864 KB
case29 593 ms 126908 KB
case30 510 ms 112928 KB
case31 557 ms 122956 KB
case32 510 ms 113076 KB
case33 632 ms 134376 KB
case34 652 ms 138736 KB
case35 481 ms 107744 KB
case36 582 ms 127748 KB
case37 493 ms 106432 KB
case38 495 ms 109308 KB
case39 639 ms 137200 KB
case40 504 ms 112148 KB
case41 712 ms 138072 KB
case42 718 ms 137532 KB
case43 724 ms 138876 KB
case44 725 ms 138036 KB
case45 720 ms 138132 KB
case46 534 ms 116280 KB
case47 635 ms 127560 KB
case48 554 ms 119432 KB
case49 793 ms 137544 KB
case50 576 ms 122568 KB
case51 577 ms 122208 KB
case52 583 ms 121804 KB
case53 488 ms 107772 KB
case54 494 ms 108904 KB
sample00 474 ms 106864 KB
sample01 482 ms 106060 KB
sample02 478 ms 106620 KB