101202024-03-27 16:53:04111Maximum felosztáscpp17Időlimit túllépés 40/1001.078s53028 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva4ms2524 KiB
subtask210/10
3Elfogadva3ms2076 KiB
4Elfogadva3ms2364 KiB
5Elfogadva3ms2556 KiB
6Elfogadva3ms2508 KiB
7Elfogadva3ms2820 KiB
8Elfogadva3ms2716 KiB
subtask315/15
9Elfogadva3ms2756 KiB
10Elfogadva3ms2912 KiB
11Elfogadva3ms3152 KiB
12Elfogadva3ms3200 KiB
13Elfogadva3ms3124 KiB
14Elfogadva3ms3400 KiB
15Elfogadva4ms3384 KiB
16Elfogadva3ms3620 KiB
17Elfogadva3ms3836 KiB
18Elfogadva3ms3780 KiB
subtask415/15
19Elfogadva4ms4416 KiB
20Elfogadva4ms4600 KiB
21Elfogadva4ms4956 KiB
22Elfogadva4ms4808 KiB
23Elfogadva4ms5440 KiB
24Elfogadva4ms5468 KiB
25Elfogadva4ms5600 KiB
26Elfogadva4ms5760 KiB
27Elfogadva8ms6208 KiB
28Elfogadva13ms6200 KiB
29Elfogadva4ms6000 KiB
30Elfogadva8ms6044 KiB
31Elfogadva4ms6008 KiB
32Elfogadva8ms6036 KiB
33Elfogadva6ms6028 KiB
34Elfogadva9ms6208 KiB
35Elfogadva4ms6240 KiB
36Elfogadva7ms6328 KiB
37Elfogadva4ms6092 KiB
38Elfogadva4ms6256 KiB
subtask50/60
39Időlimit túllépés1.052s18500 KiB
40Elfogadva361ms27720 KiB
41Elfogadva370ms28776 KiB
42Elfogadva203ms21760 KiB
43Elfogadva204ms21352 KiB
44Elfogadva254ms40804 KiB
45Elfogadva142ms31936 KiB
46Elfogadva758ms30972 KiB
47Elfogadva806ms41272 KiB
48Elfogadva736ms33200 KiB
49Elfogadva790ms43508 KiB
50Elfogadva739ms37180 KiB
51Elfogadva277ms35012 KiB
52Elfogadva870ms43796 KiB
53Elfogadva787ms46448 KiB
54Időlimit túllépés1.072s27656 KiB
55Időlimit túllépés1.059s32616 KiB
56Elfogadva699ms46420 KiB
57Elfogadva693ms47612 KiB
58Időlimit túllépés1.072s41488 KiB
59Időlimit túllépés1.062s42696 KiB
60Elfogadva203ms48416 KiB
61Időlimit túllépés1.065s39840 KiB
62Időlimit túllépés1.062s40760 KiB
63Időlimit túllépés1.07s40400 KiB
64Időlimit túllépés1.059s43784 KiB
65Időlimit túllépés1.074s42660 KiB
66Időlimit túllépés1.074s46744 KiB
67Időlimit túllépés1.078s51220 KiB
68Időlimit túllépés1.062s47152 KiB
69Időlimit túllépés1.074s51144 KiB
70Elfogadva820ms53028 KiB
71Időlimit túllépés1.067s47728 KiB