Submission #111037

#	Time	Username	Problem	Language	Result	Execution time	Memory
111037		square1001	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	89 ms	5108 KiB

bridge

#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
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();
	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] < A[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 = 1LL << 62;
	for(int i = 0; i < (K == 1 ? 1 : N); ++i) {
		ans = min(ans, da[i] + db[i]);
	}
	cout << ans + offset + N << endl;
	return 0;
}

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