oj.uz

Submission #48191

# Submission time Handle Problem Language Result Execution time Memory
48191 2018-05-10T13:42:51 Z E869120 Palembang Bridges (APIO15_bridge) C++14
63 / 100
 2000 ms 8624 KB 
#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;
}

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);
		for (int i = 0; i < Z.size(); i++) {
			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]; ans = min(ans, D);
			for (int j = 0; j < vec.size(); j++) {
				ans = min(ans, D);
				D += J*(vec[j].first - cx);
				J += vec[j].second; cx = vec[j].first;
			}
		}
		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 'int main()':
bridge.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < Z.size(); i++) {
                   ~~^~~~~~~~~~
bridge.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < vec.size(); j++) {
                    ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 684 KB Output is correct
2 Correct 2 ms 684 KB Output is correct
3 Correct 2 ms 684 KB Output is correct
4 Correct 3 ms 684 KB Output is correct
5 Correct 3 ms 684 KB Output is correct
6 Correct 3 ms 684 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 73 ms 6840 KB Output is correct
13 Correct 160 ms 6840 KB Output is correct
14 Correct 116 ms 6840 KB Output is correct
15 Correct 93 ms 6840 KB Output is correct
16 Correct 104 ms 6840 KB Output is correct
17 Correct 134 ms 6840 KB Output is correct
18 Correct 132 ms 6844 KB Output is correct
19 Correct 156 ms 6856 KB Output is correct
20 Correct 117 ms 6864 KB Output is correct
21 Correct 147 ms 6876 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6876 KB Output is correct
2 Correct 2 ms 6876 KB Output is correct
3 Correct 2 ms 6876 KB Output is correct
4 Correct 3 ms 6876 KB Output is correct
5 Correct 2 ms 6876 KB Output is correct
6 Correct 2 ms 6876 KB Output is correct
7 Correct 2 ms 6876 KB Output is correct
8 Correct 3 ms 6876 KB Output is correct
9 Correct 3 ms 6876 KB Output is correct
10 Correct 3 ms 6876 KB Output is correct
11 Correct 3 ms 6876 KB Output is correct
12 Correct 3 ms 6876 KB Output is correct
13 Correct 40 ms 6876 KB Output is correct
14 Correct 157 ms 6876 KB Output is correct
15 Correct 155 ms 6876 KB Output is correct
16 Correct 5 ms 6876 KB Output is correct
17 Correct 45 ms 6876 KB Output is correct
18 Correct 21 ms 6876 KB Output is correct
19 Correct 12 ms 6876 KB Output is correct
20 Correct 160 ms 6876 KB Output is correct
21 Correct 86 ms 6876 KB Output is correct
22 Correct 226 ms 6876 KB Output is correct
23 Correct 87 ms 6876 KB Output is correct
24 Correct 212 ms 6876 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6876 KB Output is correct
2 Correct 2 ms 6876 KB Output is correct
3 Correct 2 ms 6876 KB Output is correct
4 Correct 3 ms 6876 KB Output is correct
5 Correct 3 ms 6876 KB Output is correct
6 Correct 2 ms 6876 KB Output is correct
7 Correct 2 ms 6876 KB Output is correct
8 Correct 3 ms 6876 KB Output is correct
9 Correct 3 ms 6876 KB Output is correct
10 Correct 4 ms 6876 KB Output is correct
11 Correct 3 ms 6876 KB Output is correct
12 Correct 3 ms 6876 KB Output is correct
13 Correct 32 ms 6876 KB Output is correct
14 Correct 155 ms 6876 KB Output is correct
15 Correct 160 ms 6876 KB Output is correct
16 Correct 5 ms 6876 KB Output is correct
17 Correct 58 ms 6876 KB Output is correct
18 Correct 21 ms 6876 KB Output is correct
19 Correct 12 ms 6876 KB Output is correct
20 Correct 159 ms 6876 KB Output is correct
21 Correct 84 ms 6876 KB Output is correct
22 Correct 234 ms 6876 KB Output is correct
23 Correct 84 ms 6876 KB Output is correct
24 Correct 238 ms 6876 KB Output is correct
25 Execution timed out 2079 ms 8624 KB Time limit exceeded
26 Halted 0 ms 0 KB -