#include <bits/stdc++.h>
using namespace std;
#define task "15_bridge"
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define ll long long
#define F first
#define S second
template<class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) {
x = y;
return true;
}
return false;
}
typedef pair<int, int> ii;
int k, numCitizen;
vector<ii> citizen;
ll ans = 0;
namespace sub12 {
vector<int> pos;
void solve() {
int n = (int)citizen.size();
if (n == 0) {
cout << ans << "\n";
return;
}
FOR(i, 0, n - 1) {
pos.push_back(citizen[i].F);
pos.push_back(citizen[i].S);
}
sort(pos.begin(), pos.end());
n = pos.size();
int x = pos[n / 2];
ll res = 0;
for (ii p : citizen) {
res += 1LL * abs(x - p.F) + 1LL * abs(x - p.S);
}
cout << ans + res << "\n";
}
}
namespace sub3 {
vector<int> pos;
void solve() {
int n = (int)citizen.size();
if (n == 0) {
cout << ans << "\n";
return;
}
FOR(i, 0, n - 1) {
pos.push_back(citizen[i].F);
pos.push_back(citizen[i].S);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
ll res = LLONG_MAX;
for (int x : pos) {
for (int y : pos) {
if (x == y) continue;
ll cur = 0;
for (ii p : citizen) {
cur += min(abs(x - p.F) + abs(x - p.S), abs(y - p.F) + abs(y - p.S));
}
minimize(res, cur);
}
}
cout << ans + res << "\n";
}
}
int main() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> k >> numCitizen;
FOR(i, 1, numCitizen) {
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if (a == b) ans += 1LL * abs(x - y);
else {
ans++;
citizen.push_back({x, y});
}
}
if (k == 1) sub12::solve();
else if (k == 2 && numCitizen <= 100) sub3::solve();
return 0;
}
Compilation message (stderr)
bridge.cpp: In function 'int main()':
bridge.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |