제출 #48221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48221		square1001	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2071 ms	3824 KiB

bridge

#include <cmath>
#include <string>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, K;
	cin >> K >> N;
	long long curs = 0;
	vector<int> a, b;
	for (int i = 0; i < N; i++) {
		string sa, sb; int va, vb;
		cin >> sa >> va >> sb >> vb;
		if (va > vb) swap(va, vb);
		if (sa == sb) curs += vb - va;
		else {
			a.push_back(va);
			b.push_back(vb);
		}
	}
	N = a.size();
	if (K == 1) {
		vector<int> pv;
		pv.insert(pv.end(), a.begin(), a.end());
		pv.insert(pv.end(), b.begin(), b.end());
		sort(pv.begin(), pv.end());
		long long ret = curs + N;
		for (int i = 0; i < N; i++) {
			ret += abs(a[i] - pv[N]) + abs(b[i] - pv[N]);
		}
		cout << ret << '\n';
	}
	else {
		long long ret = (N == 0 ? 0 : 1LL << 60);
		vector<int> plus(N);
		for (int i = 0; i < N; i++) plus[i] = a[i] + b[i];
		sort(plus.begin(), plus.end());
		for (int i = 0; i < N; i++) {
			vector<int> pva, pvb;
			for (int j = 0; j < N; j++) {
				if (a[j] + b[j] < plus[i]) {
					pva.push_back(a[j]);
					pva.push_back(b[j]);
				}
				else {
					pvb.push_back(a[j]);
					pvb.push_back(b[j]);
				}
			}
			sort(pva.begin(), pva.end());
			sort(pvb.begin(), pvb.end());
			long long sum = 0;
			for (int j = 0; j < N; j++) {
				if (a[j] + b[j] < plus[i]) {
					sum += abs(a[j] - pva[pva.size() / 2]) + abs(b[j] - pva[pva.size() / 2]);
				}
				else {
					sum += abs(a[j] - pvb[pvb.size() / 2]) + abs(b[j] - pvb[pvb.size() / 2]);
				}
			}
			ret = min(ret, sum);
		}
		cout << N + ret + curs << '\n';
	}
	return 0;
}

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