이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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+1){
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=6;
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;
}
컴파일 시 표준 에러 (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++){
| ~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |