oj.uz

Submission #848002

# Submission time Handle Problem Language Result Execution time Memory
848002 2023-09-11T02:01:37 Z qqspeed20015 Palembang Bridges (APIO15_bridge) C++14
100 / 100
 103 ms 8800 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 344 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 476 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 42 ms 6848 KB Output is correct
13 Correct 89 ms 7704 KB Output is correct
14 Correct 61 ms 6940 KB Output is correct
15 Correct 51 ms 5056 KB Output is correct
16 Correct 59 ms 7028 KB Output is correct
17 Correct 80 ms 8028 KB Output is correct
18 Correct 71 ms 7868 KB Output is correct
19 Correct 88 ms 7980 KB Output is correct
20 Correct 74 ms 7460 KB Output is correct
21 Correct 76 ms 7676 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 2 ms 344 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 544 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 54 ms 6340 KB Output is correct
26 Correct 66 ms 7360 KB Output is correct
27 Correct 91 ms 7440 KB Output is correct
28 Correct 102 ms 8800 KB Output is correct
29 Correct 103 ms 7804 KB Output is correct
30 Correct 53 ms 4312 KB Output is correct
31 Correct 64 ms 6876 KB Output is correct
32 Correct 87 ms 7948 KB Output is correct
33 Correct 84 ms 7764 KB Output is correct
34 Correct 92 ms 7872 KB Output is correct
35 Correct 72 ms 7360 KB Output is correct
36 Correct 93 ms 7908 KB Output is correct
37 Correct 43 ms 6336 KB Output is correct