87722024-01-29 18:22:59NagyLeoKutyavetélkedőpypy3Wrong answer 85/100409ms190628 KiB
def max_points(K, N, M, pairs):
    can_do = [set() for i in range(K + 1)]
    for a, b in pairs:
        can_do[a].add(b)

    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):
        if T[i] > K:
            continue
        if T[i + 1] in can_do[T[i]]:
            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])

    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))
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted41ms77032 KiB
2Accepted46ms76664 KiB
subtask20/15
3Accepted50ms77104 KiB
4Accepted46ms77568 KiB
5Accepted43ms78156 KiB
6Accepted46ms78044 KiB
7Wrong answer119ms144220 KiB
8Accepted118ms143812 KiB
9Accepted107ms144420 KiB
subtask319/19
10Accepted46ms78964 KiB
11Accepted43ms78648 KiB
12Accepted46ms78740 KiB
13Accepted48ms79076 KiB
14Accepted50ms78912 KiB
15Accepted48ms79304 KiB
16Accepted50ms79872 KiB
subtask434/34
17Accepted101ms94004 KiB
18Accepted101ms94272 KiB
19Accepted108ms94308 KiB
20Accepted104ms95332 KiB
21Accepted103ms95852 KiB
22Accepted112ms96268 KiB
subtask532/32
23Accepted223ms123380 KiB
24Accepted226ms127524 KiB
25Accepted244ms133992 KiB
26Accepted230ms138096 KiB
27Accepted250ms138288 KiB
28Accepted300ms150528 KiB
29Accepted402ms190628 KiB
30Accepted409ms190484 KiB
31Accepted266ms159512 KiB
32Accepted190ms138204 KiB
33Accepted307ms176680 KiB
34Accepted307ms176372 KiB