Submission #109968

#	Time	Username	Problem	Language	Result	Execution time	Memory
109968		Saboon	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2044 ms	3312 KiB

bridge

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;
const ll inf = 1e18;

vector<pair<int, int> > eve;
vector<ll> places;
ll Answer = inf;

ll calculate(int i, int j){
	ll sum = 0;
	for (auto k : eve){
		ll tmp = min(abs(k.first - places[i]) + abs(k.second - places[i]),
				abs(k.first - places[j]) + abs(k.second - places[j]));
		sum += tmp;
	}
	return sum;
}

void find(int L, int R, int l, int r){
	if (L >= R)
		return;
	int mid = (L + R) >> 1;
	ll k = inf, idx = -1;
	for (int i = l; i < min(mid, r); i++){
		ll tmp = calculate(i, mid);
		if (tmp < k){
			k = tmp;
			idx = i;
		}
	}
	Answer = min(Answer, k);
	find(L, mid, l, idx + 1);
	find(mid + 1, R, idx, r);
}

ll solve(){
	int n = eve.size();
	vector<ll> a(2 * n + 1);
	for (int i = 0; i < n; i++){
		a[2 * i + 0 + 1] = eve[i].first;
		a[2 * i + 1 + 1] = eve[i].second;
	}
	sort(a.begin() + 1, a.end());
	n = 2 * n;
	for (int i = 1; i <= n; i++)
		a[i] += a[i - 1];
	ll answer = inf;
	for (int i = 1; i <= n; i++){
		ll T = a[i] - a[i - 1];
		answer = min(answer, T * (i - (n - i)) - a[i] + (a[n] - a[i])); 
	}
	return answer + eve.size();
}

int main(){
	ios_base::sync_with_stdio(false);
	int k, n;
	cin >> k >> n;
	ll answer = 0;
	for (int i = 0; i < n; i++){
		int x, y;
		char a, b;
		cin >> a >> x >> b >> y;
		if (a == b){
			answer += abs(x - y);
			continue;
		}
		if (a == 'B')
			swap(x, y);
		eve.push_back({x, y});
	}
	if (eve.empty())
		return cout << answer << endl, 0;
	if (k == 1){
		cout << answer + solve() << '\n';
		return 0;
	}
	for (int i = 0; i < eve.size(); i++){
		places.push_back(eve[i].first);
		places.push_back(eve[i].second);
	}
	sort(places.begin(), places.end());
	int m = places.size();
	find(0, m, 0, m);
	cout << Answer + answer + eve.size() << endl;
	return 0;
}

Compilation message (stderr)

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

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