Submission #279708

#	Time	Username	Problem	Language	Result	Execution time	Memory
279708		srvlt	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	49 ms	4596 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 1e5 + 123;
int n, k, m, l[n0], r[n0];
ll ans;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> k >> n;
	for (int i = 0; i < n; i++) {
		char c1, c2;
		int L, R;
		cin >> c1 >> L >> c2 >> R;
		if (L > R) swap(L, R);
		ans += R - L;
		if (c1 != c2) {
			l[m] = L, r[m] = R;
			m++;
		}
	}
	if (k == 1) {
		vector <int> v;
		for (int i = 0; i < m; i++)
			v.pb(l[i]), v.pb(r[i]);
		sort(all(v));
		int j = SZ(v) / 2;
		for (int i = 0; i < m; i++) {
			if (v[j] < l[i]) ans += 2 * (l[i] - v[j]);
			if (r[i] < v[j]) ans += 2 * (v[j] - r[i]);
		}
	}
	cout << ans + m;
}

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