#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define SZ(x) int(x.size())
#define X first
#define Y second
#define mid ((l+r)>>1)
const int MXN = 2e5+5;
int n, m, V[MXN], C[MXN];
struct DS {
set<pii> s1, s2;
ll sum;
DS(): sum(0) {}
inline void insert(pii x) {
sum += x.X;
s2.insert(x);
if(SZ(s2)==m+1) {
sum -= s2.begin()->X;
s1.insert(*s2.begin());
s2.erase(s2.begin());
}
}
inline void erase(pii x) {
if(s1.find(x)!=s1.end()) s1.erase(x);
else {
sum -= x.X;
s2.erase(x);
if(SZ(s2)<m && !s1.empty()) {
sum += s1.rbegin()->X;
s2.insert(*s1.rbegin());
s1.erase(prev(s1.end()));
}
}
}
} ds;
int L, R;
inline void add(int i) { ds.insert({V[i], i}); }
inline void rem(int i) { ds.erase({V[i], i}); }
inline void adjust(int l, int r) {
while(R<r) add(++R);
while(L>l) add(--L);
while(R>r) rem(R--);
while(L<l) rem(L++);
}
inline ll cost() { return ds.sum - 2*C[R] + 2*C[L]; }
ll dp[MXN];
int opt[MXN];
void rec(int l, int r, int opl, int opr) {
if(l>r) return;
dp[mid] = -1e18;
for(int i=max(opl, mid+m-1); i<=opr; i++) {
adjust(mid, i);
if(cost()>dp[mid]) {
dp[mid] = cost();
opt[mid] = i;
}
}
rec(mid+1, r, opt[mid], opr);
rec(l, mid-1, opl, opt[mid]);
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> m;
vector<pii> vec(n);
for(int i=0; i<n; i++)
cin >> vec[i].Y >> vec[i].X;
sort(vec.begin(), vec.end());
for(int i=0; i<n; i++)
V[i+1] = vec[i].Y, C[i+1] = vec[i].X;
L = 1;
rec(1, n+1-m, 1, n);
cout << *max_element(dp+1, dp+n+2-m) << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |