Submission #853059

#	Time	Username	Problem	Language	Result	Execution time	Memory
853059		aymanrs	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	43 ms	4308 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int k, n, a, b;cin >> k >> n;
	char c,h;
	long long sl = 0, ans = LONG_LONG_MAX, cur = 0, tans = 0;
	vector<pair<int, bool>> e;
	while(n--){
		cin >> c >> a >> h >> b;
		if(a>b)swap(a,b);
		tans += b-a;
		if(c==h) continue;
		tans++;
		e.emplace_back(a, false);
		e.emplace_back(b, true);
	}
	if(e.empty()){
		cout << tans << '\n';
		return;
	}
	sort(e.begin(), e.end());
	for(int i = 0;i < e.size();i++){
		if(!e[i].second) {
			sl -= 2;
			cur += 2*(e[i].first-e[0].first);
		}
	}
	int pr = e[0].first;
	for(auto p : e){
		cur += sl*(p.first-pr);
		pr = p.first;
		ans = min(ans, cur);
		sl += 2;
	}
	cout << ans+tans << '\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message (stderr)

bridge.cpp: In function 'void solve()':
bridge.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0;i < e.size();i++){
      |                ~~^~~~~~~~~~

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