이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
#define PB push_back
int N,M;
pair<LL,LL> CV[200000];
pair<LL,int> V[200000];
int main(){
cin >> N >> M;
if(N > 2000) return -1;
for(int i=0; i<N; i++){
cin >> CV[i].second >> CV[i].first;
}
sort(CV, CV+N);
for(int i=0; i<N; i++){
V[i] = MP(CV[i].second,i);
}
sort(V, V+N);
//
LL now = -(CV[N-1].first-CV[0].first)*2;
multiset<int> use;
for(int i=0; i<M; i++){
now += V[N-1-i].first;
use.insert(V[N-1-i].second);
}
priority_queue<pair<LL,int>> que;
for(int i=M; i<N; i++){
que.push(V[N-1-i]);
}
LL maximum = now;
LL r = N;
for(int i=N-1; i>=M; i--){
now += 2*(CV[i].first-CV[i-1].second);
if(use.count(i) == 1){
use.erase(i);
now -= CV[i].second;
while(que.top().second >= i) que.pop();
now += que.top().first;
use.insert(que.top().second);
que.pop();
}
if(maximum < now){
maximum = now;
r = i;
}
}
//
now = -(CV[N-1].first-CV[0].first)*2;
use.clear();
for(int i=0; i<M; i++){
now += V[N-1-i].first;
use.insert(V[N-1-i].second);
}
while(!que.empty()) que.pop();
for(int i=M; i<N; i++){
que.push(V[N-1-i]);
}
maximum = now;
LL l = -1;
for(int i=0; i<N-M; i++){
now += 2*(CV[i+1].first-CV[i].second);
if(use.count(i) == 1){
use.erase(i);
now -= CV[i].second;
while(que.top().second >= i) que.pop();
now += que.top().first;
use.insert(que.top().second);
que.pop();
}
if(maximum < now){
maximum = now;
l = i;
}
}
//
vector<LL> v;
LL ans = -(CV[r-1].first-CV[l+1].first)*2;
for(int i=l+1; i<=r-1; i++){
v.PB(CV[i].second);
}
sort(v.begin(), v.end());
for(int i=0; i<M; i++) ans += v[v.size()-1-i];
cout << l << " " << r << endl;
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |