Submission #884831

#	Time	Username	Problem	Language	Result	Execution time	Memory
884831		Hakiers	Palembang Bridges (APIO15_bridge)	C++17	17 / 100	2101 ms	4296 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e5 + 7;
constexpr ll oo = 2e18;
ll total;
pair<ll, ll> T[MAXN];
vector<ll> Z;
int n, k;

ll check(ll l, ll r){
	ll res = 0;
	
	
	for(int i = 1; i <= n; i++){
		if(T[i].first == -1) continue;
		if(T[i].first <= l && l <= T[i].second) continue;
		if(T[i].first <= r && r <= T[i].second) continue;
		
		ll cost1 = min(abs(T[i].first - l), abs(T[i].second-l));
		ll cost2 = min(abs(T[i].first - r), abs(T[i].second-r));
		res += 2*min(cost1, cost2);
	}
	return res;
}

ll solve(){
	ll res = oo;
	
	if(k == 2){
	for(int i = 0; i < Z.size(); i++)
		for(int j = i; j < Z.size(); j++)
			res = min(res, check(Z[i], Z[j]));
	}
	else {
		for(int j = 0; j < Z.size(); j++)
				res = min(res, check(Z[j], Z[j]));
	}

	return res;
}

int main(){
	cin >> k >> n;
	
	for(int i = 1; i <= n; i++){
		char x, y;
		ll a, b;
		cin >> x >> a >> y >> b;
		if(b < a) swap(a, b);
		if(x != y){
			total += (b-a+1);
			T[i] = {a, b};
		}
		else{
			total += (b-a);
			T[i] = {-1, -1};
		}
		Z.push_back(a);
		Z.push_back(b);
	}
	
	sort(Z.begin(), Z.end());
	
	
	cout << total + solve() << "\n";
}

Compilation message (stderr)

bridge.cpp: In function 'll solve()':
bridge.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < Z.size(); i++)
      |                 ~~^~~~~~~~~~
bridge.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = i; j < Z.size(); j++)
      |                  ~~^~~~~~~~~~
bridge.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int j = 0; j < Z.size(); j++)
      |                  ~~^~~~~~~~~~

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