Submission #114330

#	Time	Username	Problem	Language	Result	Execution time	Memory
114330		Bruteforceman	Palembang Bridges (APIO15_bridge)	C++11	49 / 100	2062 ms	2788 KiB

bridge

#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;

vector <pii> v;
long long pre[1000010], suf[1000010];

bool cmp(pii a, pii b) {
	return a.first + a.second < b.first + b.second;
}

long long solver(vector <pii> u) {
	vector <int> a;
	for(auto i : u) {
		a.push_back(i.first);
		a.push_back(i.second);
	}
	sort(a.begin(), a.end());
	long long ans = 0;
	for(int i : a) {
		ans += abs(a[a.size() / 2] - i);
	}
	return ans;
}

int main(int argc, char const *argv[])
{
	int k, n;
	scanf("%d %d", &k, &n);
	
	long long add = 0;
	for(int i = 1; i <= n; i++) {
		char p, q;
		int s, t;
		scanf(" %c %d %c %d", &p, &s, &q, &t);
		if(p == q) {
			add += abs(s - t);
		} else {
			add += 1;
			if(s > t) swap(s, t);
			v.push_back(pii(s, t));
		}
	}
	if(v.size() == 0) {
		printf("%lld\n", add);
		exit(0);
	}
	sort(v.begin(), v.end(), cmp);
	vector <pii> u;
	for(int i = 0; i < v.size(); i++) {
		u.push_back(v[i]);
		pre[i] = solver(u);
	}
	u.clear();
	for(int i = v.size() - 1; i >= 0; i--) {
		u.push_back(v[i]);
		suf[i] = solver(u);
	}
	long long ans = LLONG_MAX;
	if(k == 2) {
		for(int i = 0; i < v.size(); i++) {
			ans = min(ans, pre[i] + suf[i + 1]);
		}
	} else {
		ans = pre[v.size() - 1];
	}
	printf("%lld\n", ans + add);
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main(int, const char**)':
bridge.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
bridge.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
bridge.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &k, &n);
  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d", &p, &s, &q, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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