#include <bits/stdc++.h> using namespace std; #define ll long long #define eb emplace_back #define pb push_back #define fi first #define se second #define ii pair<int,int> #define ve vector #define all(x) x.begin(), x.end() #define fo(i,a,b) for (int i=(a); i<=(b); ++i) #define fd(i,a,b) for (int i=(a); i>=(b); --i) #define maxi(a, b) a = max(a, b) #define mini(a, b) a = min(a, b) #define siz(x) ((int)(x).size()) #define vi ve<int> #define _ << ' ' << const int N = 5e5+5, inf = 1e9+10, mod = 1e9+7; bool MBE; /** **/ struct BIT { ll f[N]; void upd(int x, ll v) { for (; x; x-=x&-x) { f[x] += v; } } ll get(int x) { ll res = 0; for (; x<N; x+=x&-x) { res += f[x]; } return res; } int topk(int k) { int l=1, r=2e5, mid, res=-1; while (l <= r) { mid=(l+r)/2; if (get(mid)>=k) res=mid, l=mid+1; else r=mid-1; } return res; } } cnt, sum; int n, m, cl=1, cr=0; ii a[N]; vi z; ll ans=0; void upd(int p, int v) { cnt.upd(a[p].fi,v); sum.upd(a[p].fi,v*z[a[p].fi-1]); } ll cost(int l, int r) { int nx=min(r-l+1,m); while (cl<l) upd(cl++,-1); while (cr>r) upd(cr--,-1); while (cl>l) upd(--cl,1); while (cr<r) upd(++cr,1); int pos=cnt.topk(nx), tim=nx-cnt.get(pos+1); return sum.get(pos+1)+1LL*tim*z[pos-1]-2LL*(a[r].se-a[l].se); } void dnc(int l, int r, int optl, int optr) { if (l>r) return; int mid=(l+r)/2; pair<ll,int> best={-1e18,-1}; fo(i,optl,min(mid-m+1,optr)) { best=max(best,pair<ll,int>{cost(i,mid),i}); } maxi(ans,best.fi); if (best.se==-1) best.se=optl; dnc(l,mid-1,optl,best.se); dnc(mid+1,r,best.se,optr); } void sol() { cin >> n >> m; fo(i,1,n) { cin >> a[i].fi >> a[i].se; z.pb(a[i].fi); } sort(all(z)); z.resize(unique(all(z))-z.begin()); sort(a+1, a+n+1, [&](ii x, ii y)->bool{ if (x.se==y.se) return 0; return x.se<y.se; }); fo(i,1,n) { a[i].fi=lower_bound(all(z),a[i].fi)-z.begin()+1; } dnc(1,n,1,n); cout << ans; } bool MED; signed main(){ ios::sync_with_stdio(0); cin.tie(0); if(fopen("A.inp","r")) { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); } int tc = 1; // cin >> tc; fo(i,1,tc) sol(); // cerr << "Memory = " << abs(&MED - &MBE)/1024.0/1024.0 << " MB"; return 0; }

cake3.cpp: In function 'int main()':
cake3.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen("A.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
cake3.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen("A.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~