Submission #8,778

2024-01-29 19:00:30

pypy3

Accepted 100/100

493ms

200136 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	48ms	76612 KiB
		2	Accepted	48ms	77180 KiB
subtask2	15/15
		3	Accepted	48ms	77396 KiB
		4	Accepted	46ms	77648 KiB
		5	Accepted	48ms	77824 KiB
		6	Accepted	46ms	77560 KiB
		7	Accepted	123ms	143760 KiB
		8	Accepted	142ms	143804 KiB
		9	Accepted	126ms	144004 KiB
subtask3	19/19
		10	Accepted	39ms	78116 KiB
		11	Accepted	46ms	78480 KiB
		12	Accepted	43ms	78600 KiB
		13	Accepted	41ms	79624 KiB
		14	Accepted	46ms	79516 KiB
		15	Accepted	43ms	79848 KiB
		16	Accepted	48ms	79860 KiB
subtask4	34/34
		17	Accepted	97ms	93396 KiB
		18	Accepted	103ms	94524 KiB
		19	Accepted	103ms	95876 KiB
		20	Accepted	104ms	95944 KiB
		21	Accepted	105ms	95772 KiB
		22	Accepted	119ms	97700 KiB
subtask5	32/32
		23	Accepted	212ms	130240 KiB
		24	Accepted	238ms	135968 KiB
		25	Accepted	233ms	140684 KiB
		26	Accepted	256ms	144608 KiB
		27	Accepted	277ms	146724 KiB
		28	Accepted	342ms	166452 KiB
		29	Accepted	493ms	199836 KiB
		30	Accepted	456ms	200136 KiB
		31	Accepted	287ms	176972 KiB
		32	Accepted	230ms	149400 KiB
		33	Accepted	324ms	184616 KiB
		34	Accepted	361ms	184592 KiB