#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
int main() {
int K, n;
cin >> K >> n;
vector<pair<int, int>> citizens;
int basicCost = 0;
for (int i = 0;i < n; ++i) {
int x, y;
char a, b;
cin >> a >> x >> b >> y;
if (a == b) {
basicCost += abs(x-y);
} else {
basicCost += 1;
if (x > y) citizens.push_back({y, x});
else citizens.push_back({x, y});
}
}
sort(citizens.begin(), citizens.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first + a.second < b.first + b.second;
});
vector<array<int, 3>> points;
points.push_back({0, -1, -1}); // add a fake point for easy boundary handling.
for (int i = 0; i < citizens.size(); ++i) {
points.push_back({citizens[i].first, 0, i});
points.push_back({citizens[i].second, 1, i});
}
sort(points.begin(), points.end());
/*
cerr << "init, bcost:" << basicCost << " citizens:" << citizens.size() << endl;
for (auto p : points) {
cerr << "dist:" << p[0] << " pt:" << p[1] << " idx:" << p[2] << endl;
}
*/
long long rightCost = 0;
for (auto& ctz : citizens) {
rightCost += ctz.first + ctz.second;
}
int rightIndex = 0;
int rightBehind = 0, rightAhead = citizens.size();
while (rightBehind < rightAhead) {
++rightIndex;
rightCost += (rightBehind - rightAhead) * 2 * (points[rightIndex][0] - points[rightIndex - 1][0]);
if (points[rightIndex][1] == 0) rightAhead -= 1;
else if (points[rightIndex][1] == 1) rightBehind += 1;
}
if (K == 1) {
cout << rightCost + basicCost << endl;
return 0;
}
int bestCost = rightCost;
int leftCost = 0, leftIndex = 0, leftAhead = 0, leftBehind = 0;
for (int mid = 0; mid + 1 < citizens.size(); ++mid) {
// cerr << "----- " << "round " << mid << endl;
// Reduce the effect of mid from right side.
if (array<int, 3>({citizens[mid].first, 0, mid}) > points[rightIndex]) {
rightAhead -= 1;
rightCost -= citizens[mid].first + citizens[mid].second - 2 * points[rightIndex][0];
} else if (array<int, 3>({citizens[mid].second, 1, mid}) <= points[rightIndex]) {
rightBehind -= 1;
rightCost -= - (citizens[mid].first + citizens[mid].second) + 2 * points[rightIndex][0];
} else {
rightCost -= citizens[mid].second - citizens[mid].first;
}
while (rightBehind < rightAhead) {
rightIndex += 1;
rightCost += (rightBehind - rightAhead) * 2 * (points[rightIndex][0] - points[rightIndex - 1][0]);
if (points[rightIndex][2] > mid) {
if (points[rightIndex][1] == 0) rightAhead -= 1;
else rightBehind += 1;
}
}
// Add the cost of newly added stuff.
if (array<int, 3>({citizens[mid].first, 0, mid}) > points[leftIndex]) {
leftAhead += 1;
leftCost += citizens[mid].first + citizens[mid].second - 2 * points[leftIndex][0];
} else if (array<int, 3>({citizens[mid].second, 1, mid}) <= points[leftIndex]) {
leftBehind += 1;
leftCost += - (citizens[mid].first + citizens[mid].second) + 2 * points[leftIndex][0];
} else {
leftCost += citizens[mid].second - citizens[mid].first;
}
while (leftBehind < leftAhead) {
leftIndex += 1;
leftCost += (leftBehind - leftAhead) * 2 * (points[leftIndex][0] - points[leftIndex - 1][0]);
if (points[leftIndex][2] <= mid) {
if (points[leftIndex][1] == 0) leftAhead -= 1;
else leftBehind += 1;
}
}
/*
cerr << "Round: " << mid << endl;
cerr << rightCost<< ": " << rightIndex << " " << rightAhead << ":" << rightBehind << endl;
cerr << leftCost << ": " << leftIndex << " " << leftAhead << ":" << leftBehind << endl;
*/
if (leftCost + rightCost < bestCost) {
bestCost = leftCost + rightCost;
}
}
cout << bestCost + basicCost << endl;
return 0;
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < citizens.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~
bridge.cpp:61:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int mid = 0; mid + 1 < citizens.size(); ++mid) {
| ~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
2 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
2 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
568 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
