100342024-03-25 16:25:46111Növekvő Ödön és a Másoló Varázslócpp17Wrong answer 0/100384ms524672 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;
	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();
		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
1Wrong answer3ms1860 KiB
2Runtime error209ms524672 KiB
subtask20/5
3Accepted61ms20084 KiB
4Wrong answer61ms22120 KiB
5Wrong answer61ms24060 KiB
subtask30/10
6Wrong answer3ms8676 KiB
7Wrong answer3ms8696 KiB
8Wrong answer2ms8700 KiB
subtask40/15
9Wrong answer3ms10160 KiB
10Wrong answer4ms10436 KiB
11Wrong answer4ms10280 KiB
12Wrong answer3ms10692 KiB
subtask50/5
13Wrong answer261ms401148 KiB
14Wrong answer261ms401548 KiB
15Wrong answer261ms401548 KiB
subtask60/5
16Wrong answer244ms401640 KiB
17Wrong answer194ms401736 KiB
18Wrong answer216ms401836 KiB
19Wrong answer225ms401992 KiB
subtask70/10
20Wrong answer209ms402088 KiB
21Wrong answer243ms402188 KiB
22Wrong answer243ms402504 KiB
23Wrong answer92ms152004 KiB
24Wrong answer202ms383788 KiB
subtask80/25
25Runtime error231ms522356 KiB
26Runtime error266ms522332 KiB
27Runtime error224ms522320 KiB
28Accepted3ms4484 KiB
29Runtime error224ms522284 KiB
30Runtime error219ms522276 KiB
31Runtime error266ms522020 KiB
32Runtime error219ms521896 KiB
33Runtime error224ms521880 KiB
34Runtime error266ms521864 KiB
35Runtime error222ms521616 KiB
36Runtime error222ms521616 KiB
37Runtime error223ms521624 KiB
38Runtime error268ms521616 KiB
39Runtime error225ms521604 KiB
40Runtime error268ms521364 KiB
41Runtime error224ms521356 KiB
42Runtime error206ms521356 KiB
43Runtime error266ms521340 KiB
44Runtime error225ms521320 KiB
45Runtime error225ms521320 KiB
subtask90/25
46Runtime error294ms521304 KiB
47Runtime error298ms521296 KiB
48Runtime error300ms521292 KiB
49Runtime error294ms521300 KiB
50Runtime error293ms521272 KiB
51Runtime error298ms521260 KiB
52Runtime error287ms521264 KiB
53Runtime error298ms521256 KiB
54Runtime error303ms521256 KiB
55Runtime error384ms521012 KiB