제출 #111061

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

bridge

#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 62;
long long solve(int K, int N, vector<int> A, vector<int> B) {
	vector<int> perm(N);
	for(int i = 0; i < N; ++i) perm[i] = i;
	sort(perm.begin(), perm.end(), [&](int i, int j) { return A[i] + B[i] < A[j] + B[j]; });
	vector<int> SA(N), SB(N);
	for(int i = 0; i < N; ++i) SA[i] = A[perm[i]], SB[i] = B[perm[i]];
	A = SA, B = SB;
	vector<long long> da(N + 1), db(N + 1);
	long long sum = 0, all = 0, last = -1;
	priority_queue<int> que;
	for(int i = 1; i <= N; ++i) {
		que.push(-A[i - 1]);
		que.push(-B[i - 1]);
		last = -que.top();
		que.pop();
		sum += last;
		all += A[i - 1] + B[i - 1];
		da[i] = (last * i - sum) + ((all - sum) - last * i);
	}
	sum = 0, all = 0, last = -1;
	que = priority_queue<int>();
	for(int i = 1; i <= N; ++i) {
		que.push(A[N - i]);
		que.push(B[N - i]);
		last = que.top();
		que.pop();
		sum += last;
		all += A[N - i] + B[N - i];
		db[N - i] = (sum - last * i) + (last * i - (all - sum));
	}
	long long ans = inf;
	for(int i = 0; i < (K == 1 ? 1 : N); ++i) {
		ans = min(ans, da[i] + db[i]);
	}
	return ans + N;
}
#include <cassert>
long long solve_easy(int K, int N, vector<int> A, vector<int> B) {
	assert(K == 2);
	vector<long long> cp;
	for(int i = 0; i < N; ++i) {
		cp.push_back(A[i]);
		cp.push_back(B[i]);
	}
	sort(cp.begin(), cp.end());
	long long ans = inf;
	for(int i = 0; i < 2 * N; ++i) {
		for(int j = i + 1; j < 2 * N; ++j) {
			long long sum = 0;
			for(int k = 0; k < N; ++k) {
				sum += min(abs(A[k] - cp[i]) + abs(B[k] - cp[i]), abs(A[k] - cp[j]) + abs(B[k] - cp[j]));
			}
			ans = min(ans, sum);
		}
	}
	return ans + N;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int K, N;
	cin >> K >> N;
	vector<int> A, B;
	long long offset = 0;
	for(int i = 0; i < N; ++i) {
		string P, Q; int S, T;
		cin >> P >> S >> Q >> T;
		if(P != Q) {
			A.push_back(S);
			B.push_back(T);
		}
		else offset += abs(S - T);
	}
	N = A.size();
	long long ans = solve_easy(K, N, A, B);
	cout << ans + offset << endl;
	return 0;
}

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