제출 #831766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831766		serifefedartar	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	89 ms	13588 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 18
#define MAXN 200005

vector<pair<ll,ll>> seq;
int main() {
	fast
	ll K, N;
	cin >> K >> N;

	ll sum = 0;
	for (int i = 0; i < N; i++) {
		char ch1, ch2;
		ll pos1, pos2;
		cin >> ch1 >> pos1 >> ch2 >> pos2;

		if (ch1 == ch2)
			sum += abs(pos1 - pos2);
		else
			seq.push_back({min(pos1, pos2), max(pos1, pos2)});
	}
	sort(seq.begin(), seq.end(), [&](pair<int,int> a, pair<int,int> b) {
		return a.f + a.s < b.f + b.s;
	});
	sum += seq.size();

	if (seq.size() == 0) {
		cout << sum << "\n";
		return 0;
	}

	multiset<int> s1, s2;
	ll sum1 = 0, sum2 = 0;
	for (int i = 0; i < seq.size()/2; i++) {
		s1.insert(seq[i].f);
		s1.insert(seq[i].s);
		sum1 += seq[i].f + seq[i].s;
	}
	for (int i = seq.size()/2; i < (seq.size()/2) * 2; i++) {
		s2.insert(seq[i].f);
		s2.insert(seq[i].s);
		sum2 += seq[i].f + seq[i].s;
	}
	if (seq.size() % 2) {
		s1.insert(seq[seq.size()-1].f);
		s2.insert(seq[seq.size()-1].s);
		sum1 += seq[seq.size()-1].f;
		sum2 += seq[seq.size()-1].s;
	}

	while (*(--s1.end()) > *(s2.begin())) {
		s1.insert(*(s2.begin()));
		sum1 += *(s2.begin());
		sum2 -= *(s2.begin());
		s2.erase(s2.begin());
		s2.insert(*(--s1.end()));
		sum2 += *(--s1.end());
		sum1 -= *(--s1.end());
		s1.erase(s1.find(*(--s1.end())));
	}

	ll median = *(--s1.end());
	ll ans = s1.size()*median - sum1 + sum2 - s2.size()*median + sum;
	cout << ans << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i = 0; i < seq.size()/2; i++) {
      |                  ~~^~~~~~~~~~~~~~
bridge.cpp:46:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = seq.size()/2; i < (seq.size()/2) * 2; i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~

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