Submission #331195

#	Time	Username	Problem	Language	Result	Execution time	Memory
331195		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;
    set<ii> best, reserve;
    int res = 0;
    void add(int i){
        best.insert({a[i].y, i});
        res += a[i].y;
        if (best.size()>m){
            auto it = best.begin();
            res -= it->x;
            reserve.insert(*it);
            best.erase(it);
        }
    }
    void remove(int i){
        auto it = best.find({a[i].y, i});
        if (it != best.end()){
            res -= it->x;
            best.erase(it);
            if (reserve.size()){
                auto rit = --reserve.end();
                best.insert(*rit);
                res += rit->x;
                reserve.erase(rit);
            }
        }
        else{
            reserve.erase({a[i].y, i});
        }
    }
    void update(int a, int b){
        /*if (a > r){
            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 = 0;
void solve(int l, int r, int optl, int optr){
    if (r<=l) return ;
    int i = (l+r)/2;
    int ll = max(optl, i+m-1);
    int opt = ll, bestv = 0;
    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);
    solve(i+1, r, opt, optr);
    solve(l, i, optl, opt);
}
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-m,0,n);
    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:32:24: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   32 |         if (best.size()>m){
      |             ~~~~~~~~~~~^~
cake3.cpp: In member function 'int64_t Data::get()':
cake3.cpp:66:24: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   66 |         if (best.size()<m) return -INF;
      |             ~~~~~~~~~~~^~

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