이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int K, N;
pair<int, int> arr[200100];
ll sum = 0;
bool comp(int a, int b){
return arr[a].first+arr[a].second < arr[b].first+arr[b].second;
}
priority_queue<int> pql;
priority_queue<int, vector<int>, greater<int> > pqr;
ll lsum, rsum;
ll pref[200100], suff[200100];
void insert(int val){
if (pql.empty()){
pql.push(val);
lsum += val;
return;
}
if (val > pql.top()){
if ((int)pql.size() == (int)pqr.size()){
pqr.push(val);
rsum += val;
int ins = pqr.top();
pqr.pop();
rsum -= ins;
pql.push(ins);
lsum += ins;
} else {
pqr.push(val);
rsum += val;
}
} else {
if ((int)pql.size() == (int)pqr.size()){
pql.push(val);
lsum += val;
} else {
pql.push(val);
lsum += val;
int ins = pql.top();
pql.pop();
lsum -= ins;
pqr.push(ins);
rsum += ins;
}
}
}
int main(){
cin >> K >> N;
vector<int> v;
for (int i = 1; i <= N; i++){
char ca, cb;
int pa, pb;
cin >> ca >> pa >> cb >> pb;
if (ca == cb)
sum += abs(pb-pa);
else {
v.push_back(i);
arr[i] = make_pair(pa, pb);
}
}
sort(v.begin(), v.end(), comp);
/*for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";
cout << "\n";*/
for (int i = 0; i < (int)v.size(); i++){
insert(arr[v[i]].first);
insert(arr[v[i]].second);
pref[i] = rsum-lsum+i+1;
//cout << rsum << " " << lsum << " " << pref[i] << "\n";
}
while (pql.empty()) pql.pop();
while (pqr.empty()) pqr.pop();
lsum = 0; rsum = 0;
for (int i = (int)v.size()-1; i >= 0; i--){
insert(arr[v[i]].first);
insert(arr[v[i]].second);
suff[i] = rsum-lsum+(int)v.size()-i;
//cout << rsum << " " << lsum << " " << suff[i] << "\n";
}
ll add = 0x3f3f3f3f3f3f3f3f;
for (int i = 0; i < (int)v.size()-1; i++){
add = min(add, pref[i]+suff[i+1]);
}
if (K == 1){
cout << sum+pref[v.size()-1] << "\n";
} else {
cout << sum+add;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |