Submission #108287

#	Time	Username	Problem	Language	Result	Execution time	Memory
108287		maksim_gaponov	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2041 ms	4444 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define pb push_back
typedef pair<int, int> pii;
#define F first
#define S second
#define len(x) (int)(x).size()
const int INF = 1e18;

bool cmin(int &a, const int &b) {
	if (a > b) {
		a = b;
		return 1;
	}
	return 0;
}

void run() {
	int k, n;
	cin >> k >> n;
	int ans = 0;
	vector<pii> v;
	vector<int> vals;
	for (int i = 0; i < n; ++i) {
		char a, c;
		int b, d;
		cin >> a >> b >> c >> d;
		a -= 'A';
		c -= 'A';
		if (a == c) {
			ans += abs(b - d);
		} else {
			if (a)
				swap(b, d);
			v.pb({b, d});
			vals.pb(b);
			vals.pb(d);
		}
	}
	int ans2 = INF;
	if (len(vals) == 0)
		ans2 = 0;
	for (auto x : vals) {
		int cur_ans2 = 0;
		for (auto f : v) {
			cur_ans2 += abs(f.F - x) + abs(f.S - x) + 1;
		}
		cmin(ans2, cur_ans2);
	}
	// cout << ans << ' ' << ans2 << '\n';
	cout << ans + ans2 << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

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