100342024-03-25 16:25:46111Növekvő Ödön és a Másoló Varázslócpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1860 KiB
2Futási hiba209ms524672 KiB
subtask20/5
3Elfogadva61ms20084 KiB
4Hibás válasz61ms22120 KiB
5Hibás válasz61ms24060 KiB
subtask30/10
6Hibás válasz3ms8676 KiB
7Hibás válasz3ms8696 KiB
8Hibás válasz2ms8700 KiB
subtask40/15
9Hibás válasz3ms10160 KiB
10Hibás válasz4ms10436 KiB
11Hibás válasz4ms10280 KiB
12Hibás válasz3ms10692 KiB
subtask50/5
13Hibás válasz261ms401148 KiB
14Hibás válasz261ms401548 KiB
15Hibás válasz261ms401548 KiB
subtask60/5
16Hibás válasz244ms401640 KiB
17Hibás válasz194ms401736 KiB
18Hibás válasz216ms401836 KiB
19Hibás válasz225ms401992 KiB
subtask70/10
20Hibás válasz209ms402088 KiB
21Hibás válasz243ms402188 KiB
22Hibás válasz243ms402504 KiB
23Hibás válasz92ms152004 KiB
24Hibás válasz202ms383788 KiB
subtask80/25
25Futási hiba231ms522356 KiB
26Futási hiba266ms522332 KiB
27Futási hiba224ms522320 KiB
28Elfogadva3ms4484 KiB
29Futási hiba224ms522284 KiB
30Futási hiba219ms522276 KiB
31Futási hiba266ms522020 KiB
32Futási hiba219ms521896 KiB
33Futási hiba224ms521880 KiB
34Futási hiba266ms521864 KiB
35Futási hiba222ms521616 KiB
36Futási hiba222ms521616 KiB
37Futási hiba223ms521624 KiB
38Futási hiba268ms521616 KiB
39Futási hiba225ms521604 KiB
40Futási hiba268ms521364 KiB
41Futási hiba224ms521356 KiB
42Futási hiba206ms521356 KiB
43Futási hiba266ms521340 KiB
44Futási hiba225ms521320 KiB
45Futási hiba225ms521320 KiB
subtask90/25
46Futási hiba294ms521304 KiB
47Futási hiba298ms521296 KiB
48Futási hiba300ms521292 KiB
49Futási hiba294ms521300 KiB
50Futási hiba293ms521272 KiB
51Futási hiba298ms521260 KiB
52Futási hiba287ms521264 KiB
53Futási hiba298ms521256 KiB
54Futási hiba303ms521256 KiB
55Futási hiba384ms521012 KiB