oj.uz

Submission #389802

# Submission time Handle Problem Language Result Execution time Memory
389802 2021-04-14T14:31:26 Z milleniumEeee Palembang Bridges (APIO15_bridge) C++14
31 / 100
 2000 ms 5724 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;

const int MAXN = (int)2e5 + 5;
const int INF = 1e18;

pair <char, int> st[MAXN];
pair <char, int> fn[MAXN];

bool ok(int pos) {
	return (st[pos].first == fn[pos].first);	
}

signed main() {
	fastInp;
	int n, k;
	cin >> k >> n;
	for (int i = 1; i <= n; i++) {
		cin >> st[i].fr >> st[i].sc >> fn[i].fr >> fn[i].sc;
	}
	if (k == 1) {
		int side = 0;
		int bridge = 0;
		vector <int> x;
		for (int i = 1; i <= n; i++) {
			if (ok(i)) {
				side += abs(st[i].sc - fn[i].sc);
			} else {
				x.pb(st[i].sc);
				x.pb(fn[i].sc);
			}
		}
		sort(all(x));
		int opt = x[szof(x) / 2 - 1];
		for (int el : x) {
			bridge += abs(opt - el);
		}
		cout << side + szof(x) / 2 + bridge << endl;
	}
	else if (k == 2) {
		int ans = INF;
		vector <int> vec;
		for (int i = 1; i <= n; i++) {
			vec.pb(st[i].sc);
			vec.pb(fn[i].sc);
		}
		int bb1, bb2;
		for (int b1 : vec) {
			for (int b2 : vec) {
				int cur = 0;
				for (int p = 1; p <= n; p++) {
					if (ok(p)) {
						cur += abs(st[p].sc - fn[p].sc);
					} else {
						int x = st[p].sc;
						int y = fn[p].sc;
						cur += 1 + min(abs(x - b1) + abs(y - b1), abs(x - b2) + abs(y - b2));
					}
				}
				if (ans > cur) {
					ans = cur;
					bb1 = b1;
					bb2 = b2;
				}
			}
		}
		cout << ans << endl;
		//cout << "ans: " << ans << endl;
		//cout << "b1: " << bb1 << endl;
		//cout << "b2: " << bb2 << endl;
	}
}

/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:55:7: warning: variable 'bb1' set but not used [-Wunused-but-set-variable]
   55 |   int bb1, bb2;
      |       ^~~
bridge.cpp:55:12: warning: variable 'bb2' set but not used [-Wunused-but-set-variable]
   55 |   int bb1, bb2;
      |            ^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 25 ms 5620 KB Output is correct
13 Correct 48 ms 5724 KB Output is correct
14 Correct 35 ms 5352 KB Output is correct
15 Correct 27 ms 3404 KB Output is correct
16 Correct 33 ms 5696 KB Output is correct
17 Correct 35 ms 5648 KB Output is correct
18 Correct 42 ms 5672 KB Output is correct
19 Correct 45 ms 5716 KB Output is correct
20 Correct 33 ms 5684 KB Output is correct
21 Correct 42 ms 5696 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 13 ms 328 KB Output is correct
4 Correct 13 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 15 ms 340 KB Output is correct
8 Correct 14 ms 348 KB Output is correct
9 Correct 15 ms 344 KB Output is correct
10 Correct 15 ms 332 KB Output is correct
11 Correct 15 ms 332 KB Output is correct
12 Correct 14 ms 332 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 13 ms 344 KB Output is correct
4 Correct 13 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 15 ms 332 KB Output is correct
8 Correct 15 ms 348 KB Output is correct
9 Correct 15 ms 340 KB Output is correct
10 Correct 15 ms 348 KB Output is correct
11 Correct 14 ms 344 KB Output is correct
12 Correct 15 ms 320 KB Output is correct
13 Execution timed out 2064 ms 332 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 13 ms 348 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 15 ms 344 KB Output is correct
8 Correct 15 ms 348 KB Output is correct
9 Correct 14 ms 344 KB Output is correct
10 Correct 14 ms 332 KB Output is correct
11 Correct 14 ms 332 KB Output is correct
12 Correct 14 ms 332 KB Output is correct
13 Execution timed out 2073 ms 332 KB Time limit exceeded
14 Halted 0 ms 0 KB -