This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>
using namespace std;
const int MAXN = 2e5 + 1;
const ll INF = 1e17;
int n,m;
ll color[MAXN];
ll v[MAXN];
ll dp[MAXN];
int lptr = 0;
int rptr = -1;
set<ll> s1;
set<ll> s2;
void add(int ptr){
s1.insert(v[ptr]);
if(s1.size() > m){
ll v = *s1.begin();
s1.erase(s1.begin());
s2.insert(v);
}
}
void remove(int ptr){
if(s2.size() > 0)s2.erase(s2.begin());
else s1.erase(s1.begin());
}
ll cost(int l,int r){
if(s1.size() < m)return -INF;
ll sum = 0;
for(auto e:s1)sum += e;
return sum;
/*vv<ll> a;
FORE(i,l,r)a.pb(v[i]);
sort(a.begin(),a.end());reverse(a.begin(),a.end());
if(a.size() < m)return -INF;
ll sum = 0;
FOR(i,m)sum += a[i];
return sum;*/
}
void recurse(int l,int r,int x,int y){
int mid = (l+r)/2;
ll mx = -INF;
int optj = x;
while(rptr != mid){
if(rptr > mid){
remove(rptr--);
}else{
add(++rptr);
}
}
while(lptr != x){
if(lptr > x){
add(--lptr);
}else{
remove(lptr++);
}
}
FORE(i,x,min(mid,y)){
if(i > lptr)remove(lptr++);
ll cst = cost(i,mid) - 2*(color[mid] - color[i]);
if(cst > mx){
optj = i;
mx = cst;
}
}
dp[mid] = mx;
if(l == r)return;
recurse(l,mid,x,optj);
recurse(mid+1,r,optj,y);
}
int main(){
cin >> n >> m;
vv<ii> all;
FOR(i,n){
int a,b;
cin >> a >> b;
all.pb({b,a});
}
sort(all.begin(),all.end());
FOR(i,n)color[i] = all[i].ff,v[i] = all[i].ss;
recurse(0,n-1,0,n-1);
ll mx = -INF;
FOR(i,n){
mx = max(mx,dp[i]);
}
cout << mx << endl;
return 0;
}
Compilation message (stderr)
cake3.cpp: In function 'void add(int)':
cake3.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(s1.size() > m){
~~~~~~~~~~^~~
cake3.cpp: In function 'long long int cost(int, int)':
cake3.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(s1.size() < m)return -INF;
~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |