10573 | 2024. 04. 05 14:40:29 | 111 | Az IKPC legerősebb csapata | cpp17 | Elfogadva 100/100 | 123ms | 11312 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,K;
cin>>N>>K;
vector<int>v(N+1),w(N+1);
for(int i=1;i<=N;i++){
cin>>v[i];
}
for(int i=1;i<=N;i++){
cin>>w[i];
}
vector<vector<int>>g(N+1);
vector<int>s;
for(int i=N;i>=1;i--){
while(!s.empty()&&v[s.back()]<=v[i]){
s.pop_back();
}
g[s.empty()?0:s.back()].push_back(i);
s.push_back(i);
}
if(*min_element(w.begin(),w.end())>=0){
auto dfs=[&](auto self,int i)->vector<int>{
vector<int>s;
for(int j:g[i]){
auto z=self(self,j);
if(s.size()<z.size()){
swap(s,z);
}
s.insert(s.end(),z.begin(),z.end());
}
sort(s.begin(),s.end());
if(s.empty()){
s.push_back(w[i]);
}
else{
s.back()+=w[i];
}
return s;
};
auto ans=dfs(dfs,0);
cout<<accumulate(max(ans.begin(),ans.end()-K),ans.end(),0ll)<<'\n';
return 0;
}
auto solveMin=[&](int y)->pii{
auto dfs=[&](auto self,int i)->pair<pii,pii>{
pii a{},b{};
for(int j:g[i]){
auto [p,q]=self(self,j);
a.first+=p.first;
a.second+=p.second;
if(q.first-p.first>b.first){
b.first=q.first-p.first;
b.second=q.second-p.second;
}
}
b.first+=a.first+w[i];
b.second+=a.second;
if(b.first-y>a.first){
a.first=b.first-y;
a.second=b.second+1;
}
return{a,b};
};
return dfs(dfs,0).first;
};
auto solveMax=[&](int y)->pii{
auto dfs=[&](auto self,int i)->pair<pii,pii>{
pii a{},b{};
for(int j:g[i]){
auto [p,q]=self(self,j);
a.first+=p.first;
a.second+=p.second;
if(q.first-p.first>b.first||q.first-p.first==b.first&&q.second-p.second>b.second){
b.first=q.first-p.first;
b.second=q.second-p.second;
}
}
b.first+=a.first+w[i];
b.second+=a.second;
if(b.first-y>=a.first){
a.first=b.first-y;
a.second=b.second+1;
}
return{a,b};
};
return dfs(dfs,0).first;
};
int l=0,h=1e18;
while(l<h){
int m=(l+h)/2;
auto[x,c]=solveMin(m);
if(c<=K){
h=m;
}
else{
l=m+1;
}
}
auto[x,c]=solveMax(h);
sort(w.begin()+1,w.end());
if(c<K&&w[N-K+1]<0){
int ans=0;
for(int i=N;i>N-K;i--){
ans+=w[i];
}
cout<<ans<<'\n';
return 0;
}
cout<<x+min(c,K)*h<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1892 KiB | ||||
2 | Elfogadva | 3ms | 2084 KiB | ||||
subtask2 | 9/9 | ||||||
3 | Elfogadva | 3ms | 2316 KiB | ||||
4 | Elfogadva | 3ms | 2396 KiB | ||||
5 | Elfogadva | 3ms | 2628 KiB | ||||
6 | Elfogadva | 3ms | 2832 KiB | ||||
7 | Elfogadva | 3ms | 2904 KiB | ||||
8 | Elfogadva | 3ms | 3028 KiB | ||||
9 | Elfogadva | 3ms | 3232 KiB | ||||
10 | Elfogadva | 3ms | 3132 KiB | ||||
11 | Elfogadva | 3ms | 3260 KiB | ||||
12 | Elfogadva | 3ms | 3456 KiB | ||||
subtask3 | 7/7 | ||||||
13 | Elfogadva | 3ms | 3612 KiB | ||||
14 | Elfogadva | 3ms | 3936 KiB | ||||
15 | Elfogadva | 4ms | 4256 KiB | ||||
16 | Elfogadva | 4ms | 4260 KiB | ||||
17 | Elfogadva | 4ms | 4260 KiB | ||||
18 | Elfogadva | 4ms | 4384 KiB | ||||
19 | Elfogadva | 4ms | 4472 KiB | ||||
20 | Elfogadva | 4ms | 4528 KiB | ||||
21 | Elfogadva | 4ms | 4568 KiB | ||||
subtask4 | 11/11 | ||||||
22 | Elfogadva | 27ms | 10572 KiB | ||||
23 | Elfogadva | 28ms | 10832 KiB | ||||
24 | Elfogadva | 29ms | 10824 KiB | ||||
25 | Elfogadva | 30ms | 10832 KiB | ||||
26 | Elfogadva | 30ms | 10832 KiB | ||||
27 | Elfogadva | 32ms | 10836 KiB | ||||
subtask5 | 22/22 | ||||||
28 | Elfogadva | 7ms | 4548 KiB | ||||
29 | Elfogadva | 7ms | 4576 KiB | ||||
30 | Elfogadva | 7ms | 4836 KiB | ||||
31 | Elfogadva | 7ms | 4744 KiB | ||||
32 | Elfogadva | 7ms | 4700 KiB | ||||
33 | Elfogadva | 8ms | 4740 KiB | ||||
34 | Elfogadva | 6ms | 4956 KiB | ||||
subtask6 | 51/51 | ||||||
35 | Elfogadva | 112ms | 10296 KiB | ||||
36 | Elfogadva | 115ms | 10296 KiB | ||||
37 | Elfogadva | 115ms | 10336 KiB | ||||
38 | Elfogadva | 116ms | 10212 KiB | ||||
39 | Elfogadva | 118ms | 10212 KiB | ||||
40 | Elfogadva | 123ms | 10324 KiB | ||||
41 | Elfogadva | 92ms | 10344 KiB | ||||
42 | Elfogadva | 32ms | 11312 KiB | ||||
43 | Elfogadva | 32ms | 11204 KiB | ||||
44 | Elfogadva | 103ms | 10208 KiB | ||||
45 | Elfogadva | 103ms | 10320 KiB |