105432024-04-04 20:20:33111Az IKPC legerősebb csapatacpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer3ms1832 KiB
2Accepted3ms2048 KiB
subtask20/9
3Accepted3ms2292 KiB
4Wrong answer3ms2368 KiB
5Wrong answer3ms2568 KiB
6Accepted3ms2772 KiB
7Accepted3ms2904 KiB
8Wrong answer3ms3036 KiB
9Wrong answer3ms3076 KiB
10Wrong answer3ms3184 KiB
11Wrong answer2ms3184 KiB
12Wrong answer2ms3176 KiB
subtask30/7
13Accepted10ms19328 KiB
14Wrong answer10ms17448 KiB
15Wrong answer32ms54428 KiB
16Accepted127ms216888 KiB
17Accepted170ms292716 KiB
18Wrong answer86ms146504 KiB
19Wrong answer86ms146504 KiB
20Wrong answer9ms15332 KiB
21Accepted301ms506768 KiB
subtask40/11
22Runtime error363ms1046852 KiB
23Runtime error439ms1046660 KiB
24Runtime error365ms1046620 KiB
25Runtime error361ms1046604 KiB
26Runtime error358ms1046600 KiB
27Runtime error361ms1046532 KiB
subtask50/22
28Wrong answer61ms91276 KiB
29Accepted97ms142356 KiB
30Accepted101ms147280 KiB
31Wrong answer180ms259916 KiB
32Wrong answer32ms48672 KiB
33Wrong answer156ms229024 KiB
34Wrong answer13ms21720 KiB
subtask60/51
35Runtime error360ms1045940 KiB
36Runtime error448ms1045932 KiB
37Runtime error363ms1045912 KiB
38Runtime error361ms1045892 KiB
39Runtime error363ms1045856 KiB
40Runtime error368ms1045880 KiB
41Runtime error365ms1045844 KiB
42Runtime error361ms1045864 KiB
43Runtime error363ms1045852 KiB
44Runtime error361ms1045852 KiB
45Runtime error412ms1045860 KiB