10120 2024. 03. 27 16:53:04 111 Maximum felosztás cpp17 Időlimit túllépés 40/100 1.078s 53028 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define MOD 1000000007

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<int>v(N+1),w(M+1);
	map<int,vector<int>>m;
	for(int i=1;i<=N;i++){
		cin>>v[i];
		m[v[i]].push_back(i);
	}
	for(int i=1;i<=M;i++){
		cin>>w[i];
	}
	vector<vector<int>>dp(2,vector<int>(N+1,0));
	dp[0][0]=1;
	for(int i=1;i<=M;i++){
		fill(dp[i&1].begin(),dp[i&1].end(),0);
		for(int j:m[w[i]]){
			int x=0;
			for(int k=j;k>0&&v[k]<=w[i];k--){
				x+=dp[i&1^1][k-1];
				x%=MOD;
			}
			for(int k=j;k<=N&&(k==j||v[k]<w[i]);k++){
				dp[i&1][k]+=x;
				dp[i&1][k]%=MOD;
			}
		}
		// for(int j=1;j<=N;j++){
			// cout<<setw(4)<<dp[i&1][j]<<' ';
		// }
		// cout<<'\n';
	}
	cout<<dp[M&1][N]<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 4ms 2524 KiB
subtask2 10/10
3 Elfogadva 3ms 2076 KiB
4 Elfogadva 3ms 2364 KiB
5 Elfogadva 3ms 2556 KiB
6 Elfogadva 3ms 2508 KiB
7 Elfogadva 3ms 2820 KiB
8 Elfogadva 3ms 2716 KiB
subtask3 15/15
9 Elfogadva 3ms 2756 KiB
10 Elfogadva 3ms 2912 KiB
11 Elfogadva 3ms 3152 KiB
12 Elfogadva 3ms 3200 KiB
13 Elfogadva 3ms 3124 KiB
14 Elfogadva 3ms 3400 KiB
15 Elfogadva 4ms 3384 KiB
16 Elfogadva 3ms 3620 KiB
17 Elfogadva 3ms 3836 KiB
18 Elfogadva 3ms 3780 KiB
subtask4 15/15
19 Elfogadva 4ms 4416 KiB
20 Elfogadva 4ms 4600 KiB
21 Elfogadva 4ms 4956 KiB
22 Elfogadva 4ms 4808 KiB
23 Elfogadva 4ms 5440 KiB
24 Elfogadva 4ms 5468 KiB
25 Elfogadva 4ms 5600 KiB
26 Elfogadva 4ms 5760 KiB
27 Elfogadva 8ms 6208 KiB
28 Elfogadva 13ms 6200 KiB
29 Elfogadva 4ms 6000 KiB
30 Elfogadva 8ms 6044 KiB
31 Elfogadva 4ms 6008 KiB
32 Elfogadva 8ms 6036 KiB
33 Elfogadva 6ms 6028 KiB
34 Elfogadva 9ms 6208 KiB
35 Elfogadva 4ms 6240 KiB
36 Elfogadva 7ms 6328 KiB
37 Elfogadva 4ms 6092 KiB
38 Elfogadva 4ms 6256 KiB
subtask5 0/60
39 Időlimit túllépés 1.052s 18500 KiB
40 Elfogadva 361ms 27720 KiB
41 Elfogadva 370ms 28776 KiB
42 Elfogadva 203ms 21760 KiB
43 Elfogadva 204ms 21352 KiB
44 Elfogadva 254ms 40804 KiB
45 Elfogadva 142ms 31936 KiB
46 Elfogadva 758ms 30972 KiB
47 Elfogadva 806ms 41272 KiB
48 Elfogadva 736ms 33200 KiB
49 Elfogadva 790ms 43508 KiB
50 Elfogadva 739ms 37180 KiB
51 Elfogadva 277ms 35012 KiB
52 Elfogadva 870ms 43796 KiB
53 Elfogadva 787ms 46448 KiB
54 Időlimit túllépés 1.072s 27656 KiB
55 Időlimit túllépés 1.059s 32616 KiB
56 Elfogadva 699ms 46420 KiB
57 Elfogadva 693ms 47612 KiB
58 Időlimit túllépés 1.072s 41488 KiB
59 Időlimit túllépés 1.062s 42696 KiB
60 Elfogadva 203ms 48416 KiB
61 Időlimit túllépés 1.065s 39840 KiB
62 Időlimit túllépés 1.062s 40760 KiB
63 Időlimit túllépés 1.07s 40400 KiB
64 Időlimit túllépés 1.059s 43784 KiB
65 Időlimit túllépés 1.074s 42660 KiB
66 Időlimit túllépés 1.074s 46744 KiB
67 Időlimit túllépés 1.078s 51220 KiB
68 Időlimit túllépés 1.062s 47152 KiB
69 Időlimit túllépés 1.074s 51144 KiB
70 Elfogadva 820ms 53028 KiB
71 Időlimit túllépés 1.067s 47728 KiB