Beküldés #8 776

2024-01-29 18:57:20

pypy3

Hibás válasz 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))

	Összpont	Teszt	Verdikt	Idő	Memória
subtask1	0/0
		1	Elfogadva	41ms	76648 KiB
		2	Hibás válasz	50ms	76908 KiB
subtask2	0/15
		3	Elfogadva	43ms	77508 KiB
		4	Elfogadva	41ms	78064 KiB
		5	Elfogadva	39ms	77928 KiB
		6	Elfogadva	39ms	78136 KiB
		7	Hibás válasz	119ms	143692 KiB
		8	Elfogadva	135ms	144136 KiB
		9	Elfogadva	123ms	143888 KiB
subtask3	19/19
		10	Elfogadva	48ms	78476 KiB
		11	Elfogadva	43ms	79008 KiB
		12	Elfogadva	46ms	79104 KiB
		13	Elfogadva	43ms	78744 KiB
		14	Elfogadva	39ms	79168 KiB
		15	Elfogadva	39ms	79008 KiB
		16	Elfogadva	39ms	79132 KiB
subtask4	34/34
		17	Elfogadva	101ms	93416 KiB
		18	Elfogadva	109ms	94260 KiB
		19	Elfogadva	104ms	94832 KiB
		20	Elfogadva	111ms	94788 KiB
		21	Elfogadva	108ms	94904 KiB
		22	Elfogadva	105ms	96760 KiB
subtask5	32/32
		23	Elfogadva	202ms	128860 KiB
		24	Elfogadva	237ms	135560 KiB
		25	Elfogadva	233ms	139472 KiB
		26	Elfogadva	231ms	143096 KiB
		27	Elfogadva	238ms	144836 KiB
		28	Elfogadva	312ms	165044 KiB
		29	Elfogadva	423ms	198704 KiB
		30	Elfogadva	501ms	198960 KiB
		31	Elfogadva	282ms	175728 KiB
		32	Elfogadva	228ms	148416 KiB
		33	Elfogadva	324ms	183596 KiB
		34	Elfogadva	317ms	183512 KiB