105432024-04-04 20:20:33111Az IKPC legerősebb csapatacpp17Hibás válasz 0/100448ms1046852 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]);
				dp1[i][j]=max(dp1[i][j],dp1[i][j-1]-b[j-1]+b[j]);
			}
			dp0[i][j]=max(dp0[i][j],dp1[i][j]);
		}
	}
	cout<<dp0[K][N]<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1832 KiB
2Elfogadva3ms2048 KiB
subtask20/9
3Elfogadva3ms2292 KiB
4Hibás válasz3ms2368 KiB
5Hibás válasz3ms2568 KiB
6Elfogadva3ms2772 KiB
7Elfogadva3ms2904 KiB
8Hibás válasz3ms3036 KiB
9Hibás válasz3ms3076 KiB
10Hibás válasz3ms3184 KiB
11Hibás válasz2ms3184 KiB
12Hibás válasz2ms3176 KiB
subtask30/7
13Elfogadva10ms19328 KiB
14Hibás válasz10ms17448 KiB
15Hibás válasz32ms54428 KiB
16Elfogadva127ms216888 KiB
17Elfogadva170ms292716 KiB
18Hibás válasz86ms146504 KiB
19Hibás válasz86ms146504 KiB
20Hibás válasz9ms15332 KiB
21Elfogadva301ms506768 KiB
subtask40/11
22Futási hiba363ms1046852 KiB
23Futási hiba439ms1046660 KiB
24Futási hiba365ms1046620 KiB
25Futási hiba361ms1046604 KiB
26Futási hiba358ms1046600 KiB
27Futási hiba361ms1046532 KiB
subtask50/22
28Hibás válasz61ms91276 KiB
29Elfogadva97ms142356 KiB
30Elfogadva101ms147280 KiB
31Hibás válasz180ms259916 KiB
32Hibás válasz32ms48672 KiB
33Hibás válasz156ms229024 KiB
34Hibás válasz13ms21720 KiB
subtask60/51
35Futási hiba360ms1045940 KiB
36Futási hiba448ms1045932 KiB
37Futási hiba363ms1045912 KiB
38Futási hiba361ms1045892 KiB
39Futási hiba363ms1045856 KiB
40Futási hiba368ms1045880 KiB
41Futási hiba365ms1045844 KiB
42Futási hiba361ms1045864 KiB
43Futási hiba363ms1045852 KiB
44Futási hiba361ms1045852 KiB
45Futási hiba412ms1045860 KiB