Submission #8,777

2024-01-29 18:58:35

pypy3

Wrong answer 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))

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