Submission #915695

#	Time	Username	Problem	Language	Result	Execution time	Memory
915695		tvladm2009	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	33 ms	3772 KiB

bridge

#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);
			}
		}
		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
*/

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37