#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first
#define vs second
const int mod = 1000000007;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200004;
int n , m;
vector<pair<ll,ll>> arr;
ll ans;
bool cmp(pair<int,int> a , pair<int,int> b){
if(a.vs == b.vs)return a.vf > b.vf;
return a.vs < b.vs;
}
struct item {
vector<int> left , right;
};
void unite(vector<int>& a , vector<int>& b){
vector<int> v;
for(int i : a)v.pb(i);
for(int i : b)v.pb(i);
if(v.size() < m){
return;
}
bool vis[v.size()];
memset(vis,0,sizeof vis);
int j = 0;
int last = 1;
set<pair<ll,int>> s;
ll res = 0;
ll tp[v.size()];
for(int i = 1; i < m; i++){
res += arr[v[i]].vf;
s.insert(mp(arr[v[i]].vf , i));
tp[i] = arr[v[i]].vf;
}
res -= 2*(arr[v[m-1]].vs - arr[v[0]].vs);
res += arr[v[0]].vf;
ans = max(ans , res);
//cout << res << '\n';
s.insert(mp(arr[v[0]].vf - 2*(arr[v[last]].vs - arr[v[j]].vs) , 0));
tp[0] = arr[v[0]].vf - 2*(arr[v[last]].vs - arr[v[j]].vs);
for(int i = m; i < v.size(); i++){
res -= 2*(arr[v[i]].vs - arr[v[i-1]].vs);
ll val = arr[v[i]].vf;
if(val >= ((*s.begin()).vf)){
pair<ll,int> p = *s.begin();
s.erase(s.begin());
//cout << p.vf << ' ';
res -= p.vf;
res += val;
vis[p.vs] = 1;
s.insert(mp(val, i));
tp[i] = val;
}
else vis[i] = 1;
while(j < v.size() && vis[j]){
j++;
}
last = max(last , j + 1);
while(last < v.size() && vis[last]){
last++;
}
if(s.count(mp(tp[j] , j))){
s.erase(mp(tp[j] , j));
tp[j] = arr[v[j]].vf - 2*(arr[v[last]].vs - arr[v[j]].vs);
s.insert(mp(tp[j] , j));
}
else {
while(1){
;
}
}
ans = max(ans , res);
//cout << res << '\n';
}
}
vector<int> left_merge(vector<int>& a , vector<int>& b , bool rev){
vector<int> v;
for(int i : a)v.pb(i);
for(int i : b)v.pb(i);
if(v.size() <= m){
return v;
}
if(rev)reverse(all(v));
priority_queue<pair<int,int>,vector<pair<int,int>> , greater<pair<int,int>> > pq;
ll res = 0;
for(int i = 0; i < m; i++){
res += arr[v[i]].vf;
pq.push(mp(arr[v[i]].vf , i));
if(i){
res -= 2*abs(arr[v[i]].vs - arr[v[i-1]].vs);
}
}
ll best[v.size()];
best[m-1] = res;
for(int i = m; i < v.size(); i++){
res -= 2*abs(arr[v[i]].vs - arr[v[i-1]].vs);
if(pq.top().vf < arr[v[i]].vf){
res -= pq.top().vf;
pq.pop();
pq.push(mp(arr[v[i]].vf , i));
res += arr[v[i]].vf;
}
best[i] = res;
}
int pos = m-1;
res = best[m-1];
for(int i = m; i < v.size(); i++){
if(best[i] > res){
pos = i;
res = best[i];
}
}
while(pq.size())pq.pop();
for(int i = 0; i < m; i++){
pq.push(mp(arr[v[i]].vf , v[i]));
}
for(int i = m; i < v.size(); i++){
if(pq.top().vf < arr[v[i]].vf){
pq.pop();
pq.push(mp(arr[v[i]].vf , v[i]));
}
}
vector<int> toreturn;
while(pq.size()){
toreturn.pb(pq.top().vs);
pq.pop();
}
sort(all(toreturn));
return toreturn;
}
item merge(item a , item b){
unite(a.right , b.left);
vector<int> left = left_merge(a.left , b.left , 0);
vector<int> right = left_merge(a.right , b.right , 1);
/*for(int i : left){
cout << i << ' ';
}
cout << '\n';
for(int i : right){
cout << i << ' ';
}
cout << '\n';*/
return {left , right};
}
item dnc(int l , int r){
//cout << "came" << endl;
if(l == r){
return {{l} , {l}};
}
int m = (l + r)/2;
item a = dnc(l , m);
item b = dnc(m + 1 , r);
//cout << l << ' ' << r << '\n';
return merge(a , b);
}
void solve(){
cin >> n >> m;
for(int i = 0; i < n; i++){
int x , y;
cin >> x >> y;
arr.pb(mp(x,y));
}
sort(all(arr),cmp);
ans = -1e9;
dnc(0,n-1);
cout << ans << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;
//cin >> t;
//while(t--)
solve();
}
Compilation message
cake3.cpp: In function 'void unite(std::vector<int>&, std::vector<int>&)':
cake3.cpp:32:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
32 | if(v.size() < m){
| ~~~~~~~~~^~~
cake3.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = m; i < v.size(); i++){
| ~~^~~~~~~~~~
cake3.cpp:69:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | while(j < v.size() && vis[j]){
| ~~^~~~~~~~~~
cake3.cpp:73:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | while(last < v.size() && vis[last]){
| ~~~~~^~~~~~~~~~
cake3.cpp: In function 'std::vector<int> left_merge(std::vector<int>&, std::vector<int>&, bool)':
cake3.cpp:97:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
97 | if(v.size() <= m){
| ~~~~~~~~~^~~~
cake3.cpp:117:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i = m; i < v.size(); i++){
| ~~^~~~~~~~~~
cake3.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(int i = m; i < v.size(); i++){
| ~~^~~~~~~~~~
cake3.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int i = m; i < v.size(); i++){
| ~~^~~~~~~~~~
cake3.cpp:129:6: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
129 | int pos = m-1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
