Submission #15863

#	Time	Username	Problem	Language	Result	Execution time	Memory
15863		myungwoo	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2000 ms	4936 KiB

bridge

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

#define MAXN 100005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long lld;

int K, N, M;

struct Z{
	int a, b;
} A[MAXN];

lld proc(vector <int> &arr)
{
	if (arr.empty()) return 0;
	lld ret = 0;
	sort(all(arr));
	int x = arr[sz(arr)/2];
	for (int t: arr) ret += abs(t - x);
	return ret;
}

int main()
{
	scanf("%d%d", &K, &M);
	vector <int> arr;
	lld def = 0;
	while (M--){
		char p, q; int a, b;
		scanf(" %c%d %c%d", &p, &a, &q, &b);
		if (p == q){
			def += abs(a-b);
			continue;
		}
		def++;
		if (a > b) swap(a, b);
		A[++N] = {a, b};
	}
	sort(A+1, A+N+1, [](const Z &a, const Z &b){
		return a.a+a.b < b.a+b.b;
	});
	lld ans = 1e18;
	for (int i=0;i<=N;i++){
		vector <int> arr1, arr2;
		for (int j=1;j<=N;j++)
			if (j <= i)
				arr1.pb(A[j].a), arr1.pb(A[j].b);
			else
				arr2.pb(A[j].a), arr2.pb(A[j].b);
		lld val = def + proc(arr1) + proc(arr2);
		ans = min(ans, val);
		if (K == 1) break;
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:28:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &K, &M);
                       ^
bridge.cpp:33:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d", &p, &a, &q, &b);
                                      ^

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