Submission #111094

#	Time	Username	Problem	Language	Result	Execution time	Memory
111094		square1001	Palembang Bridges (APIO15_bridge)	C++14	9 / 100	2056 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);
	if(N == 0) return 0;
	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; 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;
}
void random_gen() {
	int K = 2, N = 5;
	for(int i = 1; i <= 100; ++i) {
		vector<int> A(N), B(N);
		for(int j = 0; j < N; ++j) {
			A[j] = rand() % 1000000000;
			B[j] = rand() % 1000000000;
		}
		long long res1 = solve(K, N, A, B);
		long long res2 = solve_easy(K, N, A, B);
		if(res1 == res2) {
			cout << "K = " << K << ", N = " << N << endl;
			for(int j = 0; j < N; ++j) {
				if(j) cout << ", ";
				cout << "(" << A[j] << ", " << B[j] << ")";
			}
			cout << endl;
			cout << "Returns: " << res1 << endl;
			cout << "Answer: " << res2 << endl;
		}
	}
	cout << "Completed" << endl;
}
int main() {
	//random_gen();
	//return 0;
	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: 9 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37