Submission #8,776

2024-01-29 18:57:20

pypy3

Wrong answer 85/100

501ms

198960 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

    # print(can_do)

    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):
        # print(i)
        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	41ms	76648 KiB
		2	Wrong answer	50ms	76908 KiB
subtask2	0/15
		3	Accepted	43ms	77508 KiB
		4	Accepted	41ms	78064 KiB
		5	Accepted	39ms	77928 KiB
		6	Accepted	39ms	78136 KiB
		7	Wrong answer	119ms	143692 KiB
		8	Accepted	135ms	144136 KiB
		9	Accepted	123ms	143888 KiB
subtask3	19/19
		10	Accepted	48ms	78476 KiB
		11	Accepted	43ms	79008 KiB
		12	Accepted	46ms	79104 KiB
		13	Accepted	43ms	78744 KiB
		14	Accepted	39ms	79168 KiB
		15	Accepted	39ms	79008 KiB
		16	Accepted	39ms	79132 KiB
subtask4	34/34
		17	Accepted	101ms	93416 KiB
		18	Accepted	109ms	94260 KiB
		19	Accepted	104ms	94832 KiB
		20	Accepted	111ms	94788 KiB
		21	Accepted	108ms	94904 KiB
		22	Accepted	105ms	96760 KiB
subtask5	32/32
		23	Accepted	202ms	128860 KiB
		24	Accepted	237ms	135560 KiB
		25	Accepted	233ms	139472 KiB
		26	Accepted	231ms	143096 KiB
		27	Accepted	238ms	144836 KiB
		28	Accepted	312ms	165044 KiB
		29	Accepted	423ms	198704 KiB
		30	Accepted	501ms	198960 KiB
		31	Accepted	282ms	175728 KiB
		32	Accepted	228ms	148416 KiB
		33	Accepted	324ms	183596 KiB
		34	Accepted	317ms	183512 KiB