Submission #8,775

2024-01-29 18:54:32

pypy3

Wrong answer 0/100

448ms

199472 KiB

def max_points(K, N, M, pairs):
    can_do = [set() for i in range(N + 1)]
    for a, b in pairs:
        can_do[a].add(b)
    if T[0] > K and T[1] > K:
        return 0

    current_points = [0] * (N + 2)
    if T[N - 1] <= K:
        current_points[N - 1] = 1
    if T[N - 2] <= K:
        current_points[N - 2] = 1
        if T[N - 1] in can_do[T[N - 2]]:
            current_points[N - 2] = 2
    for i in range(N - 3, -1, -1):
        if T[i] <= K:
            current_points[i] = 1
            if T[i + 1] in can_do[T[i]]:
                current_points[i] = max(current_points[i], 1 + current_points[i + 1])
            if T[i + 2] in can_do[T[i]]:
                current_points[i] = max(current_points[i], 1 + current_points[i + 2])
        if T[i + 1] > K and T[i + 2] > K:
            return 0
        if T[i + 1] > K and T[i + 2] not in can_do[T[i]]:
            return 0
        if T[i + 1] not in can_do[T[i]] and T[i + 2] > K:
            return 0
        if T[i + 2] not in can_do[T[i]] and T[i + 1] not in can_do[T[i]] and T[i + 1] > K:
            return 0
    # print(current_points)

    return max(current_points[0], current_points[1])


N, K = map(int, input().split())
T = list(map(int, input().split()))
M = int(input())
pairs = [tuple(map(int, input().split())) for _ in range(M)]

print(max_points(K, N, M, pairs))

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	43ms	77260 KiB
		2	Accepted	41ms	77824 KiB
subtask2	0/15
		3	Accepted	39ms	77828 KiB
		4	Accepted	48ms	78356 KiB
		5	Accepted	43ms	78596 KiB
		6	Accepted	39ms	78564 KiB
		7	Accepted	119ms	149996 KiB
		8	Wrong answer	103ms	150408 KiB
		9	Wrong answer	98ms	150492 KiB
subtask3	0/19
		10	Accepted	41ms	78616 KiB
		11	Accepted	48ms	79348 KiB
		12	Accepted	43ms	78972 KiB
		13	Accepted	41ms	79376 KiB
		14	Accepted	48ms	79784 KiB
		15	Wrong answer	45ms	80128 KiB
		16	Wrong answer	48ms	80036 KiB
subtask4	0/34
		17	Wrong answer	89ms	92736 KiB
		18	Wrong answer	90ms	93596 KiB
		19	Wrong answer	93ms	94164 KiB
		20	Wrong answer	104ms	95728 KiB
		21	Wrong answer	96ms	94116 KiB
		22	Wrong answer	97ms	93972 KiB
subtask5	0/32
		23	Wrong answer	175ms	121324 KiB
		24	Wrong answer	215ms	136108 KiB
		25	Wrong answer	240ms	140976 KiB
		26	Wrong answer	222ms	143564 KiB
		27	Wrong answer	224ms	145548 KiB
		28	Wrong answer	326ms	165460 KiB
		29	Wrong answer	407ms	199472 KiB
		30	Accepted	448ms	199236 KiB
		31	Wrong answer	268ms	176512 KiB
		32	Wrong answer	207ms	149976 KiB
		33	Wrong answer	331ms	182620 KiB
		34	Accepted	344ms	183544 KiB