Beküldés #8 777

2024-01-29 18:58:35

pypy3

Hibás válasz 100/100

435ms

199444 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	76892 KiB
		2	Hibás válasz	46ms	76864 KiB
subtask2	15/15
		3	Elfogadva	43ms	77476 KiB
		4	Elfogadva	39ms	77344 KiB
		5	Elfogadva	48ms	77912 KiB
		6	Elfogadva	48ms	77724 KiB
		7	Elfogadva	136ms	143636 KiB
		8	Elfogadva	136ms	143544 KiB
		9	Elfogadva	123ms	144144 KiB
subtask3	19/19
		10	Elfogadva	41ms	78996 KiB
		11	Elfogadva	41ms	79092 KiB
		12	Elfogadva	48ms	79124 KiB
		13	Elfogadva	46ms	79380 KiB
		14	Elfogadva	43ms	79420 KiB
		15	Elfogadva	39ms	79508 KiB
		16	Elfogadva	48ms	79784 KiB
subtask4	34/34
		17	Elfogadva	103ms	93480 KiB
		18	Elfogadva	105ms	94584 KiB
		19	Elfogadva	101ms	96244 KiB
		20	Elfogadva	112ms	95980 KiB
		21	Elfogadva	108ms	95724 KiB
		22	Elfogadva	116ms	97524 KiB
subtask5	32/32
		23	Elfogadva	208ms	130032 KiB
		24	Elfogadva	234ms	136324 KiB
		25	Elfogadva	231ms	139948 KiB
		26	Elfogadva	234ms	143576 KiB
		27	Elfogadva	259ms	145204 KiB
		28	Elfogadva	344ms	165700 KiB
		29	Elfogadva	435ms	199168 KiB
		30	Elfogadva	428ms	199444 KiB
		31	Elfogadva	282ms	176676 KiB
		32	Elfogadva	226ms	148696 KiB
		33	Elfogadva	324ms	183828 KiB
		34	Elfogadva	363ms	183836 KiB