oj.uz

Submission #15864

# Submission time Handle Problem Language Result Execution time Memory
15864 2015-07-31T17:05:46 Z myungwoo Palembang Bridges (APIO15_bridge) C++14
8 / 100
 79 ms 5820 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;
lld D[MAXN], E[MAXN];

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

void proc(lld V[])
{
	if (!N) return;
	lld val = abs(A[1].a - A[1].b);
	priority_queue <int> p, q;
	int mid = A[1].a;
	if (A[1].b < mid) p.push(A[1].b);
	else q.push(-A[1].b);
	V[1] = val;
	for (int i=2;i<=N;i++){
		val += abs(mid - A[i].a) + abs(mid - A[i].b);
		if (A[i].a < mid) p.push(A[i].a);
		else q.push(-A[i].a);
		if (A[i].b < mid) p.push(A[i].b);
		else q.push(-A[i].b);
		while (sz(p) < sz(q)){
			int nxt = -q.top(); q.pop();
			p.push(mid);
			val += (nxt - mid) * sz(p) - (nxt - mid) * (sz(q) + 1);
			mid = nxt;
		}
		while (sz(p) > sz(q)+1){
			int nxt = p.top(); p.pop();
			q.push(mid);
			val += (mid - nxt) * sz(q) - (mid - nxt) * (sz(p) + 1);
			mid = nxt;
		}
		V[i] = val;
	}
}

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; }
		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;
	});
	proc(D);
	if (K == 1){ printf("%lld\n", D[N] + def + N); return 0; }
	reverse(A+1, A+N+1);
	proc(E);
	lld ans = 1e18;
	for (int i=0;i<=N;i++) ans = min(ans, def + D[i] + E[N-i] + N);
	printf("%lld\n", ans);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:50: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:55: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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Correct 0 ms 4368 KB Output is correct
6 Correct 0 ms 4368 KB Output is correct
7 Correct 0 ms 4368 KB Output is correct
8 Correct 0 ms 4368 KB Output is correct
9 Correct 0 ms 4368 KB Output is correct
10 Correct 0 ms 4368 KB Output is correct
11 Correct 0 ms 4368 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Correct 0 ms 4368 KB Output is correct
6 Correct 0 ms 4368 KB Output is correct
7 Correct 0 ms 4368 KB Output is correct
8 Correct 0 ms 4368 KB Output is correct
9 Correct 0 ms 4368 KB Output is correct
10 Correct 0 ms 4368 KB Output is correct
11 Correct 0 ms 4368 KB Output is correct
12 Correct 43 ms 5820 KB Output is correct
13 Correct 79 ms 5736 KB Output is correct
14 Correct 43 ms 5736 KB Output is correct
15 Incorrect 36 ms 5184 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Incorrect 0 ms 4368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Incorrect 0 ms 4368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Incorrect 0 ms 4368 KB Output isn't correct
6 Halted 0 ms 0 KB -