Submission #48217

#	Time	Username	Problem	Language	Result	Execution time	Memory
48217		square1001	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2053 ms	2800 KiB

bridge

#include <cmath>
#include <string>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, K;
	cin >> K >> N;
	long long curs = 0;
	vector<int> a, b;
	for (int i = 0; i < N; i++) {
		string sa, sb; int va, vb;
		cin >> sa >> va >> sb >> vb;
		if (va > vb) swap(va, vb);
		if (sa == sb) curs += vb - va;
		else {
			a.push_back(va);
			b.push_back(vb);
		}
	}
	vector<int> pv;
	pv.insert(pv.end(), a.begin(), a.end());
	pv.insert(pv.end(), b.begin(), b.end());
	sort(pv.begin(), pv.end());
	N = a.size();
	if (K == 1) {
		long long ret = (N == 0 ? 0 : 1LL << 60);
		for (int i = 0; i < pv.size(); i++) {
			long long sum = 0;
			for (int j = 0; j < N; j++) {
				sum += abs(a[j] - pv[i]) + abs(b[j] - pv[i]);
			}
			ret = min(ret, sum);
		}
		cout << N + ret + curs << '\n';
	}
	else {
		long long ret = (N == 0 ? 0 : 1LL << 60);
		for (int i = 0; i < pv.size(); i++) {
			for (int j = 0; j < i; j++) {
				long long sum = 0;
				for (int k = 0; k < N; k++) {
					if (a[i] + b[i] < pv[i] + pv[j]) {
						sum += abs(a[k] - pv[i]) + abs(b[k] - pv[i]);
					}
					else {
						sum += abs(a[k] - pv[j]) + abs(b[k] - pv[j]);
					}
				}
				ret = min(ret, sum);
			}
		}
		cout << N + ret + curs << '\n';
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:32:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < pv.size(); i++) {
                   ~~^~~~~~~~~~~
bridge.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < pv.size(); i++) {
                   ~~^~~~~~~~~~~

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