100362024-03-25 16:32:01111Növekvő Ödön és a Másoló Varázslócpp17Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Futási hiba3ms2028 KiB
subtask20/5
3Futási hiba3ms2256 KiB
4Futási hiba3ms2480 KiB
5Futási hiba2ms2556 KiB
subtask310/10
6Elfogadva3ms2760 KiB
7Elfogadva3ms2880 KiB
8Elfogadva3ms3088 KiB
subtask415/15
9Elfogadva4ms4412 KiB
10Elfogadva4ms4628 KiB
11Elfogadva3ms4368 KiB
12Elfogadva4ms4996 KiB
subtask50/5
13Futási hiba3ms3884 KiB
14Futási hiba2ms3924 KiB
15Futási hiba3ms3996 KiB
subtask60/5
16Futási hiba3ms4000 KiB
17Futási hiba3ms4128 KiB
18Futási hiba3ms4224 KiB
19Futási hiba3ms4216 KiB
subtask70/10
20Futási hiba3ms4312 KiB
21Futási hiba3ms4212 KiB
22Futási hiba3ms4588 KiB
23Futási hiba2ms4480 KiB
24Futási hiba3ms4548 KiB
subtask80/25
25Futási hiba3ms4660 KiB
26Futási hiba2ms4656 KiB
27Futási hiba2ms4552 KiB
28Elfogadva3ms4652 KiB
29Futási hiba2ms4540 KiB
30Futási hiba3ms4768 KiB
31Futási hiba2ms4764 KiB
32Futási hiba2ms4764 KiB
33Futási hiba2ms4768 KiB
34Futási hiba3ms4892 KiB
35Futási hiba2ms4980 KiB
36Futási hiba3ms5064 KiB
37Futási hiba3ms5060 KiB
38Futási hiba3ms5068 KiB
39Futási hiba3ms5060 KiB
40Futási hiba3ms5168 KiB
41Futási hiba3ms5292 KiB
42Futási hiba3ms5396 KiB
43Futási hiba3ms5524 KiB
44Futási hiba3ms5400 KiB
45Futási hiba3ms5296 KiB
subtask90/25
46Futási hiba3ms5164 KiB
47Futási hiba2ms5164 KiB
48Futási hiba2ms5268 KiB
49Futási hiba3ms5268 KiB
50Futási hiba3ms5064 KiB
51Futási hiba3ms4964 KiB
52Futási hiba3ms5060 KiB
53Futási hiba3ms5068 KiB
54Futási hiba3ms5168 KiB
55Futási hiba3ms5168 KiB