답안 #48200 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48200	2018-05-10T13:57:37 Z	E869120	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1881 ms	20308 KB

bridge

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

long long N, K, Q, A[100009], B[100009], sum;
vector<long long>Z; vector<long long>S;

long long calculate() {
	long long rem = 0;
	for (int i = 1; i <= Q; i++) {
		long long F = (1LL << 60);
		for (int j = 0; j < S.size(); j++) {
			if (A[i] <= S[j] && S[j] <= B[i]) F = 0;
			F = min(F, 2LL * min(abs(A[i] - S[j]), abs(B[i] - S[j])));
		}
		rem += F;
	}
	return sum + rem;
}

long long solve(long long pos) {
	long long rev = (1LL << 60); int i = pos;

	vector<pair<long long, long long>>vec; long long R = 0;
	for (int j = 1; j <= Q; j++) {
		if (A[j] > Z[i]) { R += 2; vec.push_back(make_pair(A[j], 2)); vec.push_back(make_pair(B[j], 2)); vec.push_back(make_pair(B[j] + A[j] - Z[i], -2)); }
	}
	sort(vec.begin(), vec.end());

	S = vector<long long>{ Z[i] };
	long long D = calculate(), J = -R, cx = Z[i]; rev = min(rev, D);
	for (int j = 0; j < vec.size(); j++) {
		rev = min(rev, D);
		D += J*(vec[j].first - cx);
		J += vec[j].second; cx = vec[j].first;
	}
	return rev;
}

int main() {
	cin >> K >> N;
	for (int i = 1; i <= N; i++) {
		char a1, b1; long long a2, b2;
		cin >> a1 >> a2 >> b1 >> b2;
		if (a1 == b1) sum += abs(a2 - b2);
		else {
			Q++; if (a2 > b2) swap(a2, b2);
			A[Q] = a2; B[Q] = b2;
			sum += (b2 - a2 + 1);
		}
	}
	for (int i = 1; i <= Q; i++) { Z.push_back(A[i]); Z.push_back(B[i]); }
	sort(Z.begin(), Z.end());
	if (Q == 0) {
		cout << sum << endl;
		return 0;
	}
	if (K == 1) {
		vector<long long>vec;
		for (int i = 1; i <= Q; i++) { vec.push_back(A[i]); vec.push_back(B[i]); }
		sort(vec.begin(), vec.end());
		
		S = vector<long long>{ vec[vec.size() / 2] };
		long long ans = calculate();
		cout << ans << endl;
	}
	if (K == 2) {
		long long ans = (1LL << 60);
		long long L = 0, R = Z.size(), C1, C2;

		for (int i = 0; i < 27; i++) {
			C1 = (L + L + R) / 3;
			C2 = (L + R + R) / 3;
			long long v1 = solve(C1);
			long long v2 = solve(C2);
			ans = min(ans, min(v1, v2));
			if (v1 > v2) { L = C1; }
			else { R = C2; }
		}
		for (int i = -3; i <= 3; i++) {
			if (C1 + i < 0 || C1 + i >= Z.size()) continue;
			ans = min(ans, solve(C1 + i));
		}
		cout << ans << endl;
	}
	return 0;
}

Compilation message

bridge.cpp: In function 'long long int calculate()':
bridge.cpp:14:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < S.size(); j++) {
                   ~~^~~~~~~~~~
bridge.cpp: In function 'long long int solve(long long int)':
bridge.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < vec.size(); j++) {
                  ~~^~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:83:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (C1 + i < 0 || C1 + i >= Z.size()) continue;
                      ~~~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	488 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	3 ms	592 KB	Output is correct
7	Correct	3 ms	592 KB	Output is correct
8	Correct	3 ms	592 KB	Output is correct
9	Correct	3 ms	592 KB	Output is correct
10	Correct	3 ms	592 KB	Output is correct
11	Correct	3 ms	592 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	592 KB	Output is correct
2	Correct	2 ms	592 KB	Output is correct
3	Correct	2 ms	648 KB	Output is correct
4	Correct	4 ms	648 KB	Output is correct
5	Correct	4 ms	648 KB	Output is correct
6	Correct	3 ms	648 KB	Output is correct
7	Correct	4 ms	648 KB	Output is correct
8	Correct	3 ms	648 KB	Output is correct
9	Correct	3 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	3 ms	648 KB	Output is correct
12	Correct	71 ms	6760 KB	Output is correct
13	Correct	164 ms	6760 KB	Output is correct
14	Correct	108 ms	6760 KB	Output is correct
15	Correct	94 ms	6760 KB	Output is correct
16	Correct	107 ms	6760 KB	Output is correct
17	Correct	136 ms	6844 KB	Output is correct
18	Correct	131 ms	6844 KB	Output is correct
19	Correct	158 ms	6888 KB	Output is correct
20	Correct	119 ms	6888 KB	Output is correct
21	Correct	160 ms	6888 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6888 KB	Output is correct
2	Correct	2 ms	6888 KB	Output is correct
3	Correct	2 ms	6888 KB	Output is correct
4	Correct	2 ms	6888 KB	Output is correct
5	Correct	2 ms	6888 KB	Output is correct
6	Correct	2 ms	6888 KB	Output is correct
7	Correct	2 ms	6888 KB	Output is correct
8	Correct	2 ms	6888 KB	Output is correct
9	Correct	3 ms	6888 KB	Output is correct
10	Correct	3 ms	6888 KB	Output is correct
11	Correct	2 ms	6888 KB	Output is correct
12	Correct	2 ms	6888 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6888 KB	Output is correct
2	Correct	2 ms	6888 KB	Output is correct
3	Correct	2 ms	6888 KB	Output is correct
4	Correct	3 ms	6888 KB	Output is correct
5	Correct	2 ms	6888 KB	Output is correct
6	Correct	2 ms	6888 KB	Output is correct
7	Correct	2 ms	6888 KB	Output is correct
8	Correct	3 ms	6888 KB	Output is correct
9	Correct	3 ms	6888 KB	Output is correct
10	Correct	3 ms	6888 KB	Output is correct
11	Correct	2 ms	6888 KB	Output is correct
12	Correct	3 ms	6888 KB	Output is correct
13	Correct	4 ms	6888 KB	Output is correct
14	Correct	11 ms	6888 KB	Output is correct
15	Correct	10 ms	6888 KB	Output is correct
16	Correct	2 ms	6888 KB	Output is correct
17	Correct	6 ms	6888 KB	Output is correct
18	Correct	4 ms	6888 KB	Output is correct
19	Correct	3 ms	6888 KB	Output is correct
20	Correct	10 ms	6888 KB	Output is correct
21	Correct	12 ms	6888 KB	Output is correct
22	Correct	14 ms	6888 KB	Output is correct
23	Correct	6 ms	6888 KB	Output is correct
24	Correct	14 ms	6888 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6888 KB	Output is correct
2	Correct	2 ms	6888 KB	Output is correct
3	Correct	2 ms	6888 KB	Output is correct
4	Correct	2 ms	6888 KB	Output is correct
5	Correct	2 ms	6888 KB	Output is correct
6	Correct	2 ms	6888 KB	Output is correct
7	Correct	2 ms	6888 KB	Output is correct
8	Correct	2 ms	6888 KB	Output is correct
9	Correct	2 ms	6888 KB	Output is correct
10	Correct	3 ms	6888 KB	Output is correct
11	Correct	2 ms	6888 KB	Output is correct
12	Correct	2 ms	6888 KB	Output is correct
13	Correct	4 ms	6888 KB	Output is correct
14	Correct	11 ms	6888 KB	Output is correct
15	Correct	10 ms	6888 KB	Output is correct
16	Correct	3 ms	6888 KB	Output is correct
17	Correct	6 ms	6888 KB	Output is correct
18	Correct	4 ms	6888 KB	Output is correct
19	Correct	3 ms	6888 KB	Output is correct
20	Correct	12 ms	6888 KB	Output is correct
21	Correct	11 ms	6888 KB	Output is correct
22	Correct	14 ms	6888 KB	Output is correct
23	Correct	8 ms	6888 KB	Output is correct
24	Correct	14 ms	6888 KB	Output is correct
25	Correct	379 ms	7024 KB	Output is correct
26	Correct	1090 ms	11224 KB	Output is correct
27	Correct	1402 ms	11264 KB	Output is correct
28	Correct	1404 ms	11264 KB	Output is correct
29	Correct	1376 ms	11276 KB	Output is correct
30	Correct	677 ms	11276 KB	Output is correct
31	Correct	124 ms	11276 KB	Output is correct
32	Correct	1275 ms	11808 KB	Output is correct
33	Correct	1615 ms	16804 KB	Output is correct
34	Correct	1881 ms	16804 KB	Output is correct
35	Correct	1016 ms	16804 KB	Output is correct
36	Correct	1756 ms	20308 KB	Output is correct
37	Correct	90 ms	20308 KB	Output is correct

답안 #48200

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 37.0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
37.0 / 37.0