10417 2024. 04. 01 23:30:16 111 Kutyavetélkedő cpp17 Elfogadva 100/100 96ms 24116 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<int>v(N+3);
	for(int i=1;i<=N;i++){
		cin>>v[i];
	}
	vector<vector<int>>g(K+2);
	int M;
	cin>>M;
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
	}
	for(int i=1;i<=K;i++){
		g[0].push_back(i);
		g[i].push_back(0);
		sort(g[i].begin(),g[i].end());
	}
	vector<int>dp(N+3,-N-2);
	dp[N+1]=-1;
	dp[N+2]=-1;
	for(int i=N;i>=0;i--){
		if(binary_search(g[v[i]].begin(),g[v[i]].end(),v[i+1])){
			dp[i]=max(dp[i],dp[i+1]+1);
		}
		if(binary_search(g[v[i]].begin(),g[v[i]].end(),v[i+2])){
			dp[i]=max(dp[i],dp[i+2]+1);
		}
	}
	cout<<max(dp[0],0ll)<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1824 KiB
2 Elfogadva 3ms 2056 KiB
subtask2 15/15
3 Elfogadva 3ms 2256 KiB
4 Elfogadva 3ms 2480 KiB
5 Elfogadva 3ms 2680 KiB
6 Elfogadva 3ms 2744 KiB
7 Elfogadva 23ms 9016 KiB
8 Elfogadva 23ms 8972 KiB
9 Elfogadva 23ms 8972 KiB
subtask3 19/19
10 Elfogadva 3ms 2956 KiB
11 Elfogadva 3ms 2984 KiB
12 Elfogadva 3ms 3060 KiB
13 Elfogadva 3ms 3060 KiB
14 Elfogadva 3ms 3052 KiB
15 Elfogadva 3ms 3188 KiB
16 Elfogadva 3ms 3264 KiB
subtask4 34/34
17 Elfogadva 3ms 3696 KiB
18 Elfogadva 4ms 3744 KiB
19 Elfogadva 4ms 4188 KiB
20 Elfogadva 4ms 4172 KiB
21 Elfogadva 6ms 4272 KiB
22 Elfogadva 6ms 4280 KiB
subtask5 32/32
23 Elfogadva 37ms 9364 KiB
24 Elfogadva 43ms 10620 KiB
25 Elfogadva 46ms 12052 KiB
26 Elfogadva 46ms 13080 KiB
27 Elfogadva 46ms 14004 KiB
28 Elfogadva 75ms 13728 KiB
29 Elfogadva 96ms 24116 KiB
30 Elfogadva 93ms 24076 KiB
31 Elfogadva 74ms 17384 KiB
32 Elfogadva 52ms 12332 KiB
33 Elfogadva 89ms 23888 KiB
34 Elfogadva 85ms 23840 KiB