Submission #921970

#	Time	Username	Problem	Language	Result	Execution time	Memory
921970		1075508020060209tc	Cake 3 (JOI19_cake3)	C++14	100 / 100	2500 ms	38536 KiB

cake3

#pragma GCC optimize("O3")
//#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
#define SZ(x) (int)(x).size()
int K;
int ksum;
multiset<int>tmst;
multiset<int>bmst;
void mINS(int v){
tmst.insert(v);
ksum+=v;
if(tmst.size()>K){
    ksum-=*(tmst.begin());
    bmst.insert(*tmst.begin());
    tmst.erase(tmst.begin());
}
}
void mDEL(int v){
if(bmst.find(v)!=bmst.end()){
    bmst.erase(bmst.find(v));
    return;
}
ksum-=v;
tmst.erase(tmst.find(v));
if(tmst.size()<K){
    if(bmst.size()){
        tmst.insert(*(bmst.rbegin()));
        ksum+=*bmst.rbegin();
        bmst.erase(prev(bmst.end()));
    }
}
}

int mlit;int mrit;


 int ans;
int n;
pair<int,int>ar[200005];
int opt[200005];
vector<pair<int,int>>targ;vector<pair<int,int>>tbrg;
void solve(vector<pair<int,int>>aarg,vector<pair<int,int>>brg){
vector<int>apt;
for(int i=0;i<aarg.size();i++){
    apt.push_back((aarg[i].first+aarg[i].second)/2);
    targ.push_back({aarg[i].first,apt.back()});
    targ.push_back({apt.back()+1,aarg[i].second});
}
tmst.clear();
bmst.clear();
ksum=0;
int Q=aarg.size();
mlit=n;
mrit=n;
mINS(ar[n].second);

for(int i=Q-1;i>=0;i--){
 //   cout<<i<<"\n";
    int qrpl=apt[i];
    int tmx=-1e12;
    while(mlit>qrpl-K+1){
        mINS(ar[--mlit].second);
    }
    while(mrit>qrpl){
        mDEL(ar[mrit--].second);
    }



    while(mlit>=brg[i].first){
        int cal=-ar[qrpl].first+ar[mlit].first+ksum;
        if(cal>=tmx){
            opt[i]=mlit;
            tmx=cal;
        }
        ans=max(ans,tmx);
        if(mlit==brg[i].first){break;}
        mINS(ar[--mlit].second);
    }
    tbrg.push_back({opt[i],brg[i].second});
    tbrg.push_back({brg[i].first,opt[i]});
  //  cout<<"ll";
}
reverse(tbrg.begin(),tbrg.end());
}



signed main(){



cin>>n>>K;
ans=-1e12;
for(int i=1;i<=n;i++){
    cin>>ar[i].second>>ar[i].first;
    ar[i].first*=2;
}
sort(ar+1,ar+n+1);
vector<pair<int,int>>vc;vector<pair<int,int>>vc2;
vc.push_back({K,n});
vc2.push_back({1,n-K+1});
int yy=18;
while(yy--){
    solve(vc,vc2);
    int ok=1;
    for(int i=0;i<vc.size();i++){
       // cout<<vc[i].first<<" "<<vc[i].second<<"   ";
        if(vc[i].first!=vc[i].second){ok=0;}
    }
//    cout<<ans<<" "<<ok<<"\n";
    if(ok){break;}
    swap(vc,targ);swap(vc2,tbrg);
    targ.clear();tbrg.clear();
}
//cout<<"hehe";
 cout<<ans<<endl;

}

Compilation message (stderr)

cake3.cpp: In function 'void mINS(long long int)':
cake3.cpp:16:15: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   16 | if(tmst.size()>K){
      |    ~~~~~~~~~~~^~
cake3.cpp: In function 'void mDEL(long long int)':
cake3.cpp:29:15: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   29 | if(tmst.size()<K){
      |    ~~~~~~~~~~~^~
cake3.cpp: In function 'void solve(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
cake3.cpp:48:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 | for(int i=0;i<aarg.size();i++){
      |             ~^~~~~~~~~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:111:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=0;i<vc.size();i++){
      |                 ~^~~~~~~~~~

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