#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<climits>
struct Myset{
std::multiset<int> d;
int64_t sum;
Myset():d{},sum(0){}
/* // implementation of some special member function, for safety (after being moved from a set will be in a valid state)
Myset(Myset const& x)=default;
Myset(Myset&& x){
*this=std::move(x);
}
Myset& operator=(Myset const& x)=default;
Myset& operator=(Myset&& x){
d=std::move(x.d);
sum=x.sum;
x.d.clear();
x.sum=0;
return *this;
}
*/
int size()const{return d.size();}
void add(int x){
sum+=x;
d.insert(x);
}
void del_small(unsigned maxsize){
while(d.size()>maxsize){
auto iter=d.begin();
sum-=*iter;
d.erase(iter);
}
}
void merge(Myset x){
sum+=x.sum;
if(x.d.size()>d.size())
std::swap(d,x.d);
for(int z:x.d)
d.insert(z);
}
};
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int n,subset_size;std::cin>>n>>subset_size;
struct Piece{
int val,depth;
};
std::vector<Piece> ps(n);
for(auto& x:ps)std::cin>>x.val>>x.depth;
int64_t ans=INT64_MIN;
{
std::sort(begin(ps),end(ps),[](Piece a,Piece b){
return a.depth<b.depth;
});
int l=0;
int r=0;
int64_t sumval=0;
while(r<subset_size)
sumval+=ps[r++].val;
while(true){
ans=std::max<int64_t>(ans,sumval-2LL*(ps[r-1].depth-ps[l].depth));
if(r==n)
break;
sumval+=ps[r++].val-ps[l++].val;
}
}
std::sort(begin(ps),end(ps),[](Piece a,Piece b){
return a.val<b.val;
});
std::map<std::pair<int,int>,Myset> m; // {depth1,index} -> set of values with depth > depth1 and < nextdepth
// (--m.end())->second is empty
for(int i=0;i<n;++i)
m.insert({{ps[i].depth,i},{}});
m.insert({{INT_MIN,-1},{}});
for(int i=0;i<n;++i){
std::pair<int,int> depth{ps[i].depth,i};
auto iter=m.find(depth);
auto pre=std::prev(iter);
#define key first
#define value second
#define depth_ first
#define index_ second
Myset lset=std::move(pre->value);
Myset rset=std::move(iter->value);
if(lset.size()==subset_size-2)
ans=std::max<int64_t>(ans,
lset.sum+ps[pre->key.index_].val+ps[iter->key.index_].val
-2LL*(iter->key.depth_-pre->key.depth_)
);
if(rset.size()==subset_size-2){
auto nxt=std::next(iter);
ans=std::max<int64_t>(ans,
rset.sum+ps[iter->key.index_].val+ps[nxt->key.index_].val
-2LL*(nxt->key.depth_-iter->key.depth_)
);
}
m.erase(iter);
if(pre->key.index_>=0){ // ignore values before leftmost non-deleted element
lset.merge(std::move(rset));
lset.add(ps[i].val);
lset.del_small(subset_size-2);
pre->value=std::move(lset);
}
#undef key
#undef value
#undef depth_
#undef index_
}
std::cout<<ans<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
