100372024-03-25 16:32:38111Növekvő Ödön és a Másoló Varázslócpp17Futási hiba 50/100307ms402184 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>100000000){
		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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1832 KiB
2Futási hiba3ms2056 KiB
subtask25/5
3Elfogadva64ms19832 KiB
4Elfogadva61ms22012 KiB
5Elfogadva59ms23888 KiB
subtask310/10
6Elfogadva3ms8340 KiB
7Elfogadva3ms8580 KiB
8Elfogadva3ms8748 KiB
subtask415/15
9Elfogadva3ms10036 KiB
10Elfogadva4ms10300 KiB
11Elfogadva4ms9816 KiB
12Elfogadva4ms10464 KiB
subtask55/5
13Elfogadva272ms400648 KiB
14Elfogadva305ms401052 KiB
15Elfogadva307ms401332 KiB
subtask65/5
16Elfogadva279ms401364 KiB
17Elfogadva219ms401628 KiB
18Elfogadva293ms401600 KiB
19Elfogadva248ms401812 KiB
subtask710/10
20Elfogadva279ms401952 KiB
21Elfogadva243ms402040 KiB
22Elfogadva239ms402184 KiB
23Elfogadva104ms151948 KiB
24Elfogadva264ms383420 KiB
subtask80/25
25Futási hiba3ms11208 KiB
26Futási hiba2ms11288 KiB
27Futási hiba3ms11364 KiB
28Elfogadva3ms11364 KiB
29Futási hiba3ms11364 KiB
30Futási hiba3ms11364 KiB
31Futási hiba3ms11496 KiB
32Futási hiba3ms11620 KiB
33Futási hiba3ms11720 KiB
34Futási hiba3ms11704 KiB
35Futási hiba3ms11688 KiB
36Futási hiba3ms11812 KiB
37Futási hiba3ms11808 KiB
38Futási hiba3ms11792 KiB
39Futási hiba2ms11692 KiB
40Futási hiba3ms11692 KiB
41Futási hiba3ms11788 KiB
42Futási hiba3ms11780 KiB
43Futási hiba3ms11916 KiB
44Futási hiba3ms12000 KiB
45Futási hiba3ms12004 KiB
subtask90/25
46Futási hiba3ms12000 KiB
47Futási hiba2ms12000 KiB
48Futási hiba3ms12096 KiB
49Futási hiba2ms12104 KiB
50Futási hiba2ms12204 KiB
51Futási hiba2ms12104 KiB
52Futási hiba2ms12100 KiB
53Futási hiba2ms12004 KiB
54Futási hiba3ms12100 KiB
55Futási hiba2ms12200 KiB