Submission #848002

#	Time	Username	Problem	Language	Result	Execution time	Memory
848002		qqspeed20015	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	103 ms	8800 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

priority_queue <long long> leftBridge;
priority_queue <long long, vector <long long>, greater <long long>> rightBridge;
long long leftSum = 0, rightSum = 0;

bool comparePriority(pair <long long, long long> firstCitizen, pair <long long, long long> secondCitizen) {
	return (firstCitizen.first + firstCitizen.second < secondCitizen.first + secondCitizen.second);
}

void insertCitizen(long long placeCoordinate) {
	long long median = leftBridge.empty() ? LLONG_MAX : leftBridge.top();
	if (placeCoordinate <= median) {
		leftBridge.push(placeCoordinate);
		leftSum += placeCoordinate;
	} else {
		rightBridge.push(placeCoordinate);
		rightSum += placeCoordinate;
	}

	int numCitizensInLeft = (int) leftBridge.size();
	int numCitizensInRight = (int) rightBridge.size();

	if (numCitizensInRight + 1 < numCitizensInLeft) {
		long long largestSmaller = leftBridge.top();
		leftBridge.pop();
		rightBridge.push(largestSmaller);
		leftSum -= largestSmaller;
		rightSum += largestSmaller;
	} else if (numCitizensInLeft < numCitizensInRight) {
		long long smallestLarger = rightBridge.top();
		rightBridge.pop();
		leftBridge.push(smallestLarger);
		rightSum -= smallestLarger;
		leftSum += smallestLarger;
	}
}

void reset() {
	priority_queue <long long> emptyFirst;
	swap(leftBridge, emptyFirst);
	priority_queue <long long, vector <long long>, greater <long long>> emptySecond;
	swap(rightBridge, emptySecond);
	leftSum = rightSum = 0;
}

int main() {
	int maxNumBridge, numCitizens;
	cin >> maxNumBridge >> numCitizens;
	vector <pair <long long, long long>> listPairOpposite = {{0, 0}};

	char firstPlace, secondPlace;
	long long firstPosition, secondPosition;
	long long actualSameSide = 0;
	while (numCitizens--) {
		cin >> firstPlace >> firstPosition >> secondPlace >> secondPosition;
		if (firstPlace == secondPlace) // Not consider because they need not use bridge
			actualSameSide += abs(firstPosition - secondPosition);
		else
			listPairOpposite.push_back(pair <long long, long long> {firstPosition, secondPosition});
	}

	// Soft by sum of 2 position (median)
	sort(listPairOpposite.begin(), listPairOpposite.end(), comparePriority);

	// All other cases must be cross bridges
	numCitizens = (int) listPairOpposite.size() - 1;
	actualSameSide += numCitizens;

	vector <long long> maxSumAbs(numCitizens + 1, 0);

	for (int indexOfCitizen = 1; indexOfCitizen <= numCitizens; indexOfCitizen++) {
		insertCitizen(listPairOpposite[indexOfCitizen].first);
		insertCitizen(listPairOpposite[indexOfCitizen].second);
		maxSumAbs[indexOfCitizen] = rightSum - leftSum;
	}

	long long actualSumAcross = maxSumAbs[numCitizens];

	if (maxNumBridge == 2) {
		reset();
		for (int indexOfCitizen = numCitizens; indexOfCitizen >= 0; indexOfCitizen--) {
			insertCitizen(listPairOpposite[indexOfCitizen].first);
			insertCitizen(listPairOpposite[indexOfCitizen].second);
			// listPairOpposite[indexOfCitizen ... numCitizens] in left. Other in right of bridge 2
			actualSumAcross = min(actualSumAcross, rightSum - leftSum + maxSumAbs[indexOfCitizen - 1]);
		}
	}

	cout << actualSameSide + actualSumAcross;
	return 0;

}

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