100362024-03-25 16:32:01111Növekvő Ödön és a Másoló Varázslócpp17Runtime error 25/1004ms5524 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	if(N*M>100000){
		return 1;
	}
	vector<int>v(N+1),w(M);
	for(int i=1;i<=N;i++){
		cin>>v[i];
	}
	for(int i=0;i<M;i++){
		cin>>w[i];
	}
	sort(w.begin(),w.end());
	vector<vector<int>>dp(N+1,vector<int>(M));
	vector<int>ans(N+1);
	for(int i=1;i<=N;i++){
		for(int j=0;j<M;j++){
			dp[i][j]=j==0?N*2:dp[i-1][j-1]+1;
			if(w[j]>v[i-1]){
				dp[i][j]=min(dp[i][j],ans[i-1]+!(v[i-1]<v[i]&&v[i]<w[j]));
			}
		}
		int j=upper_bound(w.begin(),w.end(),v[i])-w.begin();
		ans[i]=N*2;
		if(j>0){
			ans[i]=min(ans[i],dp[i][j-1]);
		}
		if(j>0){
			ans[i]=min(ans[i],dp[i-1][j-1]);
		}
		if(v[i]>v[i-1]){
			ans[i]=min(ans[i],ans[i-1]);
		}
	}
	// for(int i=1;i<=N;i++){
		// cout<<setw(4)<<ans[i]<<" | ";
		// for(int j:dp[i]){
			// cout<<setw(4)<<j<<' ';
		// }
		// cout<<'\n';
	// }
	cout<<min(ans[N],*min_element(dp[N].begin(),dp[N].end()))<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1824 KiB
2Runtime error3ms2028 KiB
subtask20/5
3Runtime error3ms2256 KiB
4Runtime error3ms2480 KiB
5Runtime error2ms2556 KiB
subtask310/10
6Accepted3ms2760 KiB
7Accepted3ms2880 KiB
8Accepted3ms3088 KiB
subtask415/15
9Accepted4ms4412 KiB
10Accepted4ms4628 KiB
11Accepted3ms4368 KiB
12Accepted4ms4996 KiB
subtask50/5
13Runtime error3ms3884 KiB
14Runtime error2ms3924 KiB
15Runtime error3ms3996 KiB
subtask60/5
16Runtime error3ms4000 KiB
17Runtime error3ms4128 KiB
18Runtime error3ms4224 KiB
19Runtime error3ms4216 KiB
subtask70/10
20Runtime error3ms4312 KiB
21Runtime error3ms4212 KiB
22Runtime error3ms4588 KiB
23Runtime error2ms4480 KiB
24Runtime error3ms4548 KiB
subtask80/25
25Runtime error3ms4660 KiB
26Runtime error2ms4656 KiB
27Runtime error2ms4552 KiB
28Accepted3ms4652 KiB
29Runtime error2ms4540 KiB
30Runtime error3ms4768 KiB
31Runtime error2ms4764 KiB
32Runtime error2ms4764 KiB
33Runtime error2ms4768 KiB
34Runtime error3ms4892 KiB
35Runtime error2ms4980 KiB
36Runtime error3ms5064 KiB
37Runtime error3ms5060 KiB
38Runtime error3ms5068 KiB
39Runtime error3ms5060 KiB
40Runtime error3ms5168 KiB
41Runtime error3ms5292 KiB
42Runtime error3ms5396 KiB
43Runtime error3ms5524 KiB
44Runtime error3ms5400 KiB
45Runtime error3ms5296 KiB
subtask90/25
46Runtime error3ms5164 KiB
47Runtime error2ms5164 KiB
48Runtime error2ms5268 KiB
49Runtime error3ms5268 KiB
50Runtime error3ms5064 KiB
51Runtime error3ms4964 KiB
52Runtime error3ms5060 KiB
53Runtime error3ms5068 KiB
54Runtime error3ms5168 KiB
55Runtime error3ms5168 KiB