이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct pii {
int l, r;
bool operator<(pii b) const { return l+r<b.l+b.r; }
};
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int K, N, M=0;
cin>>K>>N;
pii A[N];
ll B[N], s=0, w=0;
for(int i=0; i<N; i++) {
char a, b;
int l, r;
cin>>a>>l>>b>>r;
if(l>r) swap(l, r);
if(a!=b) A[M++]={l, r};
else s+=r-l;
}
s+=N=M;
sort(A, A+N);
priority_queue<int> L;
priority_queue<int, vector<int>, greater<int>> R;
auto add=[&](pii v) {
L.push(v.l), R.push(v.r);
w+=v.r-v.l;
while(L.top()>R.top()) {
int l=L.top(), r=R.top();
L.pop(), R.pop();
L.push(r), R.push(l);
w+=(l-r)*2;
}
assert(w>=0);
return w;
};
for(int i=0; i<N; i++) B[i]=add(A[i]);
w=0;
decltype(L)().swap(L);
decltype(R)().swap(R);
ll t=B[N-1];
if(K==2 && N) for(int i=N; --i;) t=min(t, add(A[i])+B[i-1]);
cout<<s+t<<'\n';
}
# | 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... |