oj.uz

Submission #15862

# Submission time Handle Problem Language Result Execution time Memory
15862 2015-07-31T16:27:05 Z myungwoo Palembang Bridges (APIO15_bridge) C++14
0 / 100
 0 ms 2804 KB 
#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 = proc(arr1) + proc(arr2);
		ans = min(ans, val);
		if (K == 1) break;
	}
	printf("%lld\n", ans + def);
}

Compilation message

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -