| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 951086 | Amaarsaa | Palembang Bridges (APIO15_bridge) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
ll Pre[100005], Suf[100005];
void DBack(multiset<ll>& A) {
auto P = A.end();
P --;
A.erase(P);
return ;
}
ll Ed(multiset<ll>&A) {
auto P = A.end();
P --;
return *P;
}
bool cmp(auto& A, auto& B) {
return A.first + A.second < B.first + B.second;
}
multiset < ll > deer, door;
ll deer_sum =0, door_sum =0;
void Insert(ll x) {
if ( door.size() == deer.size()) {
if (deer.empty() || *deer.begin() >= x) door.insert(x), door_sum += x;
else {
door_sum += *deer.begin();
deer_sum -= *deer.begin();
deer_sum += x;
door.insert(*deer.begin());
deer.erase(deer.begin());
deer.insert(x);
}
}
else {
if ( Ed(door) <= x) {
deer.insert(x);
deer_sum += x;
}
else {
deer_sum += Ed(door);
door_sum -= Ed(door);
door_sum += x;
deer.insert(Ed(door));
DBack(door);
door.insert(x);
}
}
}
int main() {
// freopen("hayfeast.in", "r", stdin);
// freopen("hayfeast.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
ll t, n, m, ans, s,sum, x, y, r, p, i, j, cnt = 0;
cin >> n >> m;
ans = 0;
sum = 0;
char ch1, ch2;
vector < ll > v;
vector < pair < ll, ll > > q;
for (i = 1; i <= m; i ++) {
cin >> ch1 >> x >> ch2 >> y;
if ( ch1 == ch2) {
ans += abs(x - y);
sum += abs(x - y);
}
else {
v.push_back(x);
v.push_back(y);
q.push_back({x, y});
}
}
sort(v.begin(), v.end());
s = v.size();
s = (s + 1)/2 - 1;
if ( n == 2) {
sort(q.begin(), q.end(), cmp);
for (i = 0; i < q.size(); i ++) {
Insert(q[i].first);
Insert(q[i].second);
if ( i % 2 == 1) s = Ed(door) + (deer_sum - door_sum);
else s = deer_sum - door_sum;
Pre[i] = s;
}
door.clear();
deer.clear();
deer_sum = door_sum =0;
ans = Pre[q.size() - 1];
for (i = q.size() - 1; i >= 0; i --) {
Insert(q[i].first);
Insert(q[i].second);
if ( i % 2 == 1) s = Ed(door) + (deer_sum - door_sum);
else s = deer_sum - door_sum;
Suf[i] = s;
if (i == 0) ans = min(ans, Suf[i]);
else ans =min(ans, Suf[i] + Pre[i - 1]);
}
cout << ans + q.size() + sum<< endl;
return 0;
}
for (i = 0; i < v.size(); i ++) {
ans = ans + abs(v[s] - v[i]);
}
cout << ans + v.size()/2<< endl;
}