100352024-03-25 16:27:53111Növekvő Ödön és a Másoló Varázslócpp17Runtime error 0/1004ms5584 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?INT_MAX: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]=INT_MAX;
		if(j>0){
			ans[i]=dp[i][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 error3ms2196 KiB
subtask20/5
3Runtime error3ms2420 KiB
4Runtime error3ms2668 KiB
5Runtime error3ms2780 KiB
subtask30/10
6Accepted2ms2780 KiB
7Wrong answer3ms2912 KiB
8Wrong answer2ms3016 KiB
subtask40/15
9Wrong answer3ms4220 KiB
10Wrong answer4ms4472 KiB
11Wrong answer3ms4092 KiB
12Wrong answer3ms4748 KiB
subtask50/5
13Runtime error2ms3508 KiB
14Runtime error3ms3684 KiB
15Runtime error3ms3704 KiB
subtask60/5
16Runtime error3ms3804 KiB
17Runtime error3ms3800 KiB
18Runtime error2ms3888 KiB
19Runtime error3ms4104 KiB
subtask70/10
20Runtime error3ms4128 KiB
21Runtime error2ms4144 KiB
22Runtime error2ms4168 KiB
23Runtime error2ms4252 KiB
24Runtime error2ms4280 KiB
subtask80/25
25Runtime error3ms4372 KiB
26Runtime error3ms4388 KiB
27Runtime error3ms4472 KiB
28Accepted2ms4336 KiB
29Runtime error3ms4384 KiB
30Runtime error3ms4488 KiB
31Runtime error3ms4508 KiB
32Runtime error2ms4524 KiB
33Runtime error2ms4536 KiB
34Runtime error2ms4552 KiB
35Runtime error2ms4664 KiB
36Runtime error3ms4672 KiB
37Runtime error3ms5040 KiB
38Runtime error3ms5188 KiB
39Runtime error3ms5292 KiB
40Runtime error3ms5392 KiB
41Runtime error3ms5384 KiB
42Runtime error3ms5400 KiB
43Runtime error3ms5332 KiB
44Runtime error3ms5476 KiB
45Runtime error3ms5584 KiB
subtask90/25
46Runtime error3ms5256 KiB
47Runtime error3ms5364 KiB
48Runtime error3ms5292 KiB
49Runtime error3ms5308 KiB
50Runtime error3ms5408 KiB
51Runtime error3ms5344 KiB
52Runtime error2ms5352 KiB
53Runtime error2ms5372 KiB
54Runtime error3ms5532 KiB
55Runtime error2ms5412 KiB