Submission #331209

#	Time	Username	Problem	Language	Result	Execution time	Memory
331209		EIMONIM	Cake 3 (JOI19_cake3)	C++14	0 / 100	1 ms	364 KiB

cake3

#include <bits/stdc++.h>
#define int int64_t
#define vi vector<int>
#define ii pair<int,int>
#define vb vector<bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vii vector<ii>
#define vvii vector<vii>
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
using namespace std;
const int INF = 1e18, MOD = 1e9 + 7;



int n,m;
vii a;
struct Data{
    int l=0,r=-1;
    multiset<int> best, reserve;
    int res = 0;
    void add(int i){
        if (best.size()==m && *best.begin() < a[i].y){
            res += a[i].y - *best.begin();
            reserve.insert(*best.begin());
            best.erase(best.begin());
            best.insert(a[i].y);
        }
        else best.insert(a[i].y), res += a[i].y;
    }
    void remove(int i){
        auto it = best.find(a[i].y);
        if (it != best.end()){
            res -= *it;
            best.erase(it);
            if (reserve.size()){
                auto rit = --reserve.end();
                best.insert(*rit);
                res += *rit;
                reserve.erase(rit);
            }
        }
        else{
            reserve.erase(a[i].y);
        }
    }
    void update(int a, int b){
        if (a > r || b < l){
            while(l<=r) remove(l++);
            l = a, r = a-1;
        }
        while(b>r) add(++r);
        while(a<l) add(--l);
        while(b<r) remove(r--);
        while(a>l) remove(l++);
    }
    int get(){
        if (best.size()<m) return -INF;
        return res;
    }
} data;
int ans = -INF;
void solve(int l, int r, int optl, int optr){
    if (r<l) return ;
    int i = (l+r)/2;
    if (optr - i+1 < m){ // cant do i
        solve(l, i-1, optl, optr);
        return ;
    }
    int ll = max(optl, i+m-1);
    int opt = optr, bestv = -INF;
    loop(j,ll,optr+1){
        data.update(i, j);
        int v = data.get() - (a[j].x - a[i].x);
        if (bestv < v){
            bestv = v;
            opt = j;
        }
    }
    chkmax(ans, bestv);
    if (bestv <= -INF/2){
        solve(l, i-1, optl, optr);
    }
    else{
        solve(l, i-1, optl, opt);
        solve(i+1, r, opt, optr);
    }
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    a.resize(n);
    loop(i,0,n) cin>>a[i].y>>a[i].x, a[i].x*=2;
    sort(all(a));
    solve(0,n-1,0,n-1);
    cout<<ans<<endl;
    return 0;
}
/*
color a
cls
g++ cake3.cpp -o a & a
5 3
2 1
4 2
6 4
8 8
10 16



*/

Compilation message (stderr)

cake3.cpp: In member function 'void Data::add(int64_t)':
cake3.cpp:30:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   30 |         if (best.size()==m && *best.begin() < a[i].y){
      |             ~~~~~~~~~~~^~~
cake3.cpp: In member function 'int64_t Data::get()':
cake3.cpp:65:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   65 |         if (best.size()<m) return -INF;
      |             ~~~~~~~~~~~^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76