105442024-04-04 20:21:35111Az IKPC legerősebb csapatacpp17Hibás válasz 0/100423ms1047084 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<int>a(N+1),b(N+1);
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	for(int i=1;i<=N;i++){
		cin>>b[i];
	}
	vector<vector<int>>dp0(K+1,vector<int>(N+1,0)),dp1(K+1,vector<int>(N+1,0));
	for(int i=1;i<=K;i++){
		for(int j=1;j<=N;j++){
			dp0[i][j]=max(dp0[i][j-1],dp0[i-1][j]);
			dp0[i][j]=max(dp0[i][j],dp0[i-1][j-1]+b[j]);
			dp1[i][j]=max(dp1[i][j],dp0[i-1][j-1]+b[j]);
			if(a[j-1]<a[j]){
				dp1[i][j]=max(dp1[i][j],dp1[i][j-1]+b[j]);
			}
			if(a[j-1]==a[j]){
				dp1[i][j]=max(dp1[i][j],dp1[i][j-1]);
			}
			dp0[i][j]=max(dp0[i][j],dp1[i][j]);
		}
	}
	cout<<dp0[K][N]<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva3ms2056 KiB
subtask20/9
3Elfogadva3ms2288 KiB
4Hibás válasz3ms2464 KiB
5Hibás válasz3ms2568 KiB
6Elfogadva3ms2776 KiB
7Elfogadva3ms2988 KiB
8Hibás válasz3ms3216 KiB
9Hibás válasz2ms3324 KiB
10Elfogadva3ms3428 KiB
11Hibás válasz3ms3512 KiB
12Hibás válasz2ms3592 KiB
subtask30/7
13Elfogadva10ms19744 KiB
14Hibás válasz9ms17504 KiB
15Hibás válasz32ms54348 KiB
16Elfogadva123ms216804 KiB
17Elfogadva164ms292708 KiB
18Hibás válasz82ms146588 KiB
19Hibás válasz82ms146588 KiB
20Hibás válasz9ms15560 KiB
21Elfogadva287ms506560 KiB
subtask40/11
22Futási hiba358ms1047084 KiB
23Futási hiba358ms1047052 KiB
24Futási hiba361ms1047032 KiB
25Futási hiba423ms1047016 KiB
26Futási hiba361ms1047016 KiB
27Futási hiba363ms1046988 KiB
subtask50/22
28Hibás válasz52ms90824 KiB
29Elfogadva81ms142016 KiB
30Elfogadva83ms146924 KiB
31Hibás válasz150ms259188 KiB
32Hibás válasz28ms47736 KiB
33Hibás válasz128ms228144 KiB
34Hibás válasz13ms20832 KiB
subtask60/51
35Futási hiba360ms1046816 KiB
36Futási hiba361ms1046776 KiB
37Futási hiba361ms1046784 KiB
38Futási hiba361ms1046756 KiB
39Futási hiba361ms1046752 KiB
40Futási hiba363ms1046744 KiB
41Futási hiba363ms1046736 KiB
42Futási hiba358ms1046752 KiB
43Futási hiba363ms1046744 KiB
44Futási hiba363ms1046744 KiB
45Futási hiba361ms1046744 KiB