101202024-03-27 16:53:04111Maximum felosztáscpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted4ms2524 KiB
subtask210/10
3Accepted3ms2076 KiB
4Accepted3ms2364 KiB
5Accepted3ms2556 KiB
6Accepted3ms2508 KiB
7Accepted3ms2820 KiB
8Accepted3ms2716 KiB
subtask315/15
9Accepted3ms2756 KiB
10Accepted3ms2912 KiB
11Accepted3ms3152 KiB
12Accepted3ms3200 KiB
13Accepted3ms3124 KiB
14Accepted3ms3400 KiB
15Accepted4ms3384 KiB
16Accepted3ms3620 KiB
17Accepted3ms3836 KiB
18Accepted3ms3780 KiB
subtask415/15
19Accepted4ms4416 KiB
20Accepted4ms4600 KiB
21Accepted4ms4956 KiB
22Accepted4ms4808 KiB
23Accepted4ms5440 KiB
24Accepted4ms5468 KiB
25Accepted4ms5600 KiB
26Accepted4ms5760 KiB
27Accepted8ms6208 KiB
28Accepted13ms6200 KiB
29Accepted4ms6000 KiB
30Accepted8ms6044 KiB
31Accepted4ms6008 KiB
32Accepted8ms6036 KiB
33Accepted6ms6028 KiB
34Accepted9ms6208 KiB
35Accepted4ms6240 KiB
36Accepted7ms6328 KiB
37Accepted4ms6092 KiB
38Accepted4ms6256 KiB
subtask50/60
39Time limit exceeded1.052s18500 KiB
40Accepted361ms27720 KiB
41Accepted370ms28776 KiB
42Accepted203ms21760 KiB
43Accepted204ms21352 KiB
44Accepted254ms40804 KiB
45Accepted142ms31936 KiB
46Accepted758ms30972 KiB
47Accepted806ms41272 KiB
48Accepted736ms33200 KiB
49Accepted790ms43508 KiB
50Accepted739ms37180 KiB
51Accepted277ms35012 KiB
52Accepted870ms43796 KiB
53Accepted787ms46448 KiB
54Time limit exceeded1.072s27656 KiB
55Time limit exceeded1.059s32616 KiB
56Accepted699ms46420 KiB
57Accepted693ms47612 KiB
58Time limit exceeded1.072s41488 KiB
59Time limit exceeded1.062s42696 KiB
60Accepted203ms48416 KiB
61Time limit exceeded1.065s39840 KiB
62Time limit exceeded1.062s40760 KiB
63Time limit exceeded1.07s40400 KiB
64Time limit exceeded1.059s43784 KiB
65Time limit exceeded1.074s42660 KiB
66Time limit exceeded1.074s46744 KiB
67Time limit exceeded1.078s51220 KiB
68Time limit exceeded1.062s47152 KiB
69Time limit exceeded1.074s51144 KiB
70Accepted820ms53028 KiB
71Time limit exceeded1.067s47728 KiB