#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5,inf=1e18,minf=-1e18,lg=20,Mxn=1e6;
//#undef int
int n,k,m,d,q;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int C[mxn+10],V[mxn+10];
struct node{
node *l,*r;
int sum,cnt;
node():l(0),r(0),sum(0),cnt(0){};
};
node *root[mxn+10];
int W[mxn+10];
void build(node *&cur,int l=0,int r=n){
cur=new node();
if(l==r)return;
int mid=(l+r)>>1;
build(cur->l,l,mid);
build(cur->r,mid+1,r);
}
void update(node *&cur,node *last,int qpos,int l=0,int r=n){
cur=new node(*last);
if(l==r){
cur->sum+=W[l];
cur->cnt++;
return;
}
int mid=(l+r)>>1;
if(qpos<=mid)update(cur->l,last->l,qpos,l,mid);
else update(cur->r,last->r,qpos,mid+1,r);
cur->cnt=cur->l->cnt+cur->r->cnt;
cur->sum=cur->l->sum+cur->r->sum;
}
int getsum(node *L,node *R,int k,int l=0,int r=n){
if(k==0)return 0;
if(R->cnt-L->cnt<=k)return R->sum-L->sum;
if(l==r)return W[l]*k;
int mid=(l+r)>>1;
return getsum(L->r,R->r,k,mid+1,r)+getsum(L->l,R->l,max(0LL,k-(R->r->cnt-L->r->cnt)),l,mid);
}
int dp[mxn+10];
int getcost(int l,int r){
return getsum(root[l-1],root[r],m)+2*C[l];
}
int32_t main(){
fastio
// 1d/1d ?
cin>>n>>m;
vector<pii>v(n);
vector<int>comp;
for(auto &i:v)cin>>i.s>>i.f,comp.pb(i.s);
sort(all(v));
sort(all(comp));
comp.erase(unique(all(comp)),comp.end());
for(auto &i:v)i.s=lb(all(comp),i.s)-comp.begin();
for(int i=0;i<comp.size();i++)W[i]=comp[i];
for(int i=0;i<n;i++)C[i+1]=v[i].f,V[i+1]=v[i].s;
build(root[0]);
for(int i=1;i<=n;i++)update(root[i],root[i-1],V[i]);
deque<pii>dq;
dq.pb({m-1,1});
//starting point,opt
int ans=minf;
for(int i=m;i<=n;i++){
if(dq.size()>1&&dq[1].f==i)dq.pop_front();
else dq[0].f++;
ans=max(ans,getcost(dq.front().s,i)-2*C[i]);
//76 23
while(!dq.empty()&&getcost(i-m+2,dq.back().f)>=getcost(dq.back().s,dq.back().f)){
dq.pop_back();
}
if(dq.empty()){
dq.pb({i,i-m+2});
continue;
}
int l=dq.back().f,r=n,pos=inf;
while(l<=r){
int mid=l+(r-l)/2;
if(getcost(dq.back().s,mid)<=getcost(i-m+2,mid))r=mid-1,pos=min(pos,mid);
else l=mid+1;
}
if(pos!=inf)dq.pb({pos,i-m+2});
}
cout<<ans;
}
/*
*/
Compilation message (stderr)
cake3.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
16 | #pragma GCC optimize ("03,unroll-lopps")
| ^
cake3.cpp:23:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
23 | void setIO(string name){
| ^
cake3.cpp:32:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
32 | node():l(0),r(0),sum(0),cnt(0){};
| ^
cake3.cpp:36:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
36 | void build(node *&cur,int l=0,int r=n){
| ^
cake3.cpp:43:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
43 | void update(node *&cur,node *last,int qpos,int l=0,int r=n){
| ^
cake3.cpp:56:49: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
56 | int getsum(node *L,node *R,int k,int l=0,int r=n){
| ^
cake3.cpp:64:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
64 | int getcost(int l,int r){
| ^
cake3.cpp:67:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
67 | int32_t main(){
| ^
cake3.cpp: In function 'void setIO(std::string)':
cake3.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
