Submission #582824

#	Time	Username	Problem	Language	Result	Execution time	Memory
582824		Justin1	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	127 ms	3636 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct ppl {
	ll h,o; //house, office
	bool operator < (const ppl & x) const {
		return h+o < x.h+x.o;
	}
};

ll n,m,k,x,y,z;
vector<ll> median;
vector<ppl> city;
char st, ed;

ll cal(vector<ppl> & city, vector<ll> & median) {
	ll ans = 0;
	if (median.size()) {
		sort(median.begin(),median.end());
		ll bridge = median[median.size()/2];
		for (auto i : city) ans += abs(i.h-bridge) + abs(i.o-bridge) + 1;
	}
	return ans;
}

void sub1() {
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> st >> x >> ed >> y;
		if (st == ed) ans += abs(x-y);
		else {
			median.push_back(x);
			median.push_back(y);
			city.push_back({x,y});
		}
	}
	cout << ans + cal(city,median) << "\n";
}

void sub2() {
	ll ans = 0, mn = 1e18;
	for (int i = 1; i <= n; i++) {
		cin >> st >> x >> ed >> y;
		if (st == ed) ans += abs(x-y);
		else city.push_back({x,y});
	}
	sort(city.begin(),city.end());
	for (int i = 0; i < city.size(); i++) {
		vector<ppl> c1, c2;
		vector<ll> m1, m2;
		for (int j = 0; j < i; j++) {
			c1.push_back(city[j]);
			m1.push_back(city[j].h);
			m1.push_back(city[j].o);
		}
		for (int j = i; j < city.size(); j++) {
			c2.push_back(city[j]);
			m2.push_back(city[j].h);
			m2.push_back(city[j].o);
		}
		mn = min(mn,cal(c1,m1)+cal(c2,m2));
	}
	cout << ans + mn << "\n";
}

signed main() {
	cin >> m >> n;
	if (m == 1) sub1();
	else sub2();
}

Compilation message (stderr)

bridge.cpp: In function 'void sub2()':
bridge.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ppl>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i < city.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
bridge.cpp:57:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ppl>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (int j = i; j < city.size(); j++) {
      |                   ~~^~~~~~~~~~~~~

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