Beküldés #8 778

2024-01-29 19:00:30

pypy3

Elfogadva 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))

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