| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 915696 | tvladm2009 | Palembang Bridges (APIO15_bridge) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;
const string FILENAME = "input";
int k, n;
map<int, vector<int>> ind;
struct three {
ll first;
ll second;
ll third;
bool operator < (three oth) const {
return first > oth.first;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//read(FILENAME);
cin >> k >> n;
ll add = 0;
vector<pair<int, int>> v;
vector<int> points;
int cnt = 0;
for (int i = 1; i <= n; i++) {
char p, q;
int s, t;
cin >> p >> s >> q >> t;
if (p == q) {
add += abs(s - t);
} else {
points.pb(s);
points.pb(t);
if (p == '1') {
swap(s, t);
}
v.pb(mp(s, t));
cnt++;
}
}
sort(all(points));
if (k == 1) {
auto f = [&](int bridge) {
ll res = 0;
for (auto i: points) {
res += abs(i - bridge);
}
res += cnt;
return res;
};
int med = (sz(points) + 1) / 2;
cout << f(points[med - 1]) + add << '\n';
} else {
auto f = [&](int i, int j) {
ll res = 0;
for (auto x: v) {
res += min(abs(x.first - i) + abs(x.second - i), abs(x.first - j) + abs(x.second - j));
}
res += cnt;
return res;
};
vector<int> bridges = points;
for (int i = 0; i < sz(points); i++) {
for (int j = 0; j < sz(points); j++) {
bridges.pb((points[i] + points[j]) / 2);
bridges.pb((points[i] + points[j] + 1) / 2);
}
}
sort(all(bridges));
bridges.resize(all(bridges) - bridges.begin());
ll ans = 1e18;
for (auto i: bridges) {
for (auto j: bridges) {
chkmin(ans, f(i, j));
}
}
cout << ans + add << '\n';
return 0;
sort(all(v));
ll sum = 0;
for (auto i: v) {
sum += abs(i.second - i.first);
}
for (auto i: v) {
ind[max(i.first, i.second)].pb(min(i.first, i.second));
}
points.resize(unique(all(points)) - points.begin());
//ll ans = 1e18;
for (int i = 0; i + 1 < sz(points); i++) {
ll cost = sum;
priority_queue<three> pq;
int offset = 0;
ll inpq = 2 * (points[i + 1] - points[i]);
for (int j = i + 1; j < sz(points); j++) {
while (!pq.empty() && -pq.top().first <= offset) {
cost += pq.top().second;
inpq -= pq.top().third;
pq.pop();
}
for (auto kek: ind[points[j]]) {
if (kek >= points[i]) {
cost -= points[j] - kek;
pq.push({-(points[j] - points[i] + kek - points[i] - points[j] + kek + offset), points[j] - points[i] + kek - points[i], points[j] - kek});
inpq += points[j] - kek;
}
}
chkmin(ans, cost + inpq);
if (j == sz(points)) {
break;
}
offset += 2 * (points[j + 1] - points[j]);
}
}
cout << ans + cnt + add << '\n';
}
return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
5
2
5
5
7
*/