Submission #951091

#	Time	Username	Problem	Language	Result	Execution time	Memory
951091		Amaarsaa	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	186 ms	16608 KiB

bridge

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
ll Pre[100005], Suf[100005];

void DBack(multiset<ll>& A) {
	auto P = A.end();
	P --;
	A.erase(P);
	return ;
}
ll Ed(multiset<ll>&A) {
	auto P = A.end();
	P --;
	return *P;
}
bool cmp(pair < ll, ll >& A, pair < ll, ll >& B) {
	return A.first + A.second < B.first + B.second;
}
multiset < ll > deer, door;
ll	deer_sum =0, door_sum =0;
void Insert(ll x) {
	if ( door.size() == deer.size()) {
		if (deer.empty() || *deer.begin() >= x) door.insert(x), door_sum += x;
		else {
			door_sum += *deer.begin();
			deer_sum -= *deer.begin();
			deer_sum += x;
			door.insert(*deer.begin());
			deer.erase(deer.begin());
			deer.insert(x);
		}
	}
	else {
		if ( Ed(door) <= x) {
			deer.insert(x);
			deer_sum += x;
		}
		else {
			deer_sum += Ed(door);
			door_sum -= Ed(door);
			door_sum += x;
			deer.insert(Ed(door));
			DBack(door);
			door.insert(x);
		}
	}
} 
int main() {
//	freopen("hayfeast.in", "r", stdin);
//	freopen("hayfeast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll t, n, m, ans, s,sum, x, y, r, p, i, j, cnt = 0;

	cin >> n >> m;
	
	ans = 0;
	
	sum = 0;
	char ch1, ch2;
	vector < ll > v;
	vector < pair < ll, ll > > q;
	for (i = 1; i <= m; i ++) {
		cin >> ch1 >> x >> ch2 >> y;
		if ( ch1 == ch2) {
			ans += abs(x - y);
			sum += abs(x - y);
		}
		else {
			v.push_back(x);
			v.push_back(y);
			q.push_back({x, y});
		}
	}
	sort(v.begin(), v.end());
	s = v.size();
	s = (s + 1)/2 - 1;
	if ( n == 2) {
		sort(q.begin(), q.end(), cmp);
		
		for (i = 0; i < q.size(); i ++) {
			Insert(q[i].first);
			Insert(q[i].second);
			
			s = deer_sum - door_sum;
			Pre[i] = s;
 		}
 		door.clear();
 		deer.clear();
 		deer_sum = door_sum =0;
 		ans = Pre[q.size() - 1];
		for (i = q.size() - 1; i >= 0; i --) {
			Insert(q[i].first);
			Insert(q[i].second);
			s = deer_sum - door_sum;
			Suf[i] = s;
			if (i == 0) ans = min(ans, Suf[i]);
			else ans =min(ans, Suf[i] + Pre[i - 1]);
 		}
 		cout << ans + q.size()  + sum<< endl;
		return 0;
	}
	for (i = 0; i < v.size(); i ++) {
		ans = ans + abs(v[s] - v[i]);
	}
	cout << ans + v.size()/2<< endl;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:83:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (i = 0; i < q.size(); i ++) {
      |               ~~^~~~~~~~~~
bridge.cpp:105:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (i = 0; i < v.size(); i ++) {
      |              ~~^~~~~~~~~~
bridge.cpp:55:5: warning: unused variable 't' [-Wunused-variable]
   55 |  ll t, n, m, ans, s,sum, x, y, r, p, i, j, cnt = 0;
      |     ^
bridge.cpp:55:32: warning: unused variable 'r' [-Wunused-variable]
   55 |  ll t, n, m, ans, s,sum, x, y, r, p, i, j, cnt = 0;
      |                                ^
bridge.cpp:55:35: warning: unused variable 'p' [-Wunused-variable]
   55 |  ll t, n, m, ans, s,sum, x, y, r, p, i, j, cnt = 0;
      |                                   ^
bridge.cpp:55:41: warning: unused variable 'j' [-Wunused-variable]
   55 |  ll t, n, m, ans, s,sum, x, y, r, p, i, j, cnt = 0;
      |                                         ^
bridge.cpp:55:44: warning: unused variable 'cnt' [-Wunused-variable]
   55 |  ll t, n, m, ans, s,sum, x, y, r, p, i, j, cnt = 0;
      |                                            ^~~

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