100352024-03-25 16:27:53111Növekvő Ödön és a Másoló Varázslócpp17Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Futási hiba3ms2196 KiB
subtask20/5
3Futási hiba3ms2420 KiB
4Futási hiba3ms2668 KiB
5Futási hiba3ms2780 KiB
subtask30/10
6Elfogadva2ms2780 KiB
7Hibás válasz3ms2912 KiB
8Hibás válasz2ms3016 KiB
subtask40/15
9Hibás válasz3ms4220 KiB
10Hibás válasz4ms4472 KiB
11Hibás válasz3ms4092 KiB
12Hibás válasz3ms4748 KiB
subtask50/5
13Futási hiba2ms3508 KiB
14Futási hiba3ms3684 KiB
15Futási hiba3ms3704 KiB
subtask60/5
16Futási hiba3ms3804 KiB
17Futási hiba3ms3800 KiB
18Futási hiba2ms3888 KiB
19Futási hiba3ms4104 KiB
subtask70/10
20Futási hiba3ms4128 KiB
21Futási hiba2ms4144 KiB
22Futási hiba2ms4168 KiB
23Futási hiba2ms4252 KiB
24Futási hiba2ms4280 KiB
subtask80/25
25Futási hiba3ms4372 KiB
26Futási hiba3ms4388 KiB
27Futási hiba3ms4472 KiB
28Elfogadva2ms4336 KiB
29Futási hiba3ms4384 KiB
30Futási hiba3ms4488 KiB
31Futási hiba3ms4508 KiB
32Futási hiba2ms4524 KiB
33Futási hiba2ms4536 KiB
34Futási hiba2ms4552 KiB
35Futási hiba2ms4664 KiB
36Futási hiba3ms4672 KiB
37Futási hiba3ms5040 KiB
38Futási hiba3ms5188 KiB
39Futási hiba3ms5292 KiB
40Futási hiba3ms5392 KiB
41Futási hiba3ms5384 KiB
42Futási hiba3ms5400 KiB
43Futási hiba3ms5332 KiB
44Futási hiba3ms5476 KiB
45Futási hiba3ms5584 KiB
subtask90/25
46Futási hiba3ms5256 KiB
47Futási hiba3ms5364 KiB
48Futási hiba3ms5292 KiB
49Futási hiba3ms5308 KiB
50Futási hiba3ms5408 KiB
51Futási hiba3ms5344 KiB
52Futási hiba2ms5352 KiB
53Futási hiba2ms5372 KiB
54Futási hiba3ms5532 KiB
55Futási hiba2ms5412 KiB