oj.uz

Submission #882729

# Submission time Handle Problem Language Result Execution time Memory
882729 2023-12-03T14:44:25 Z Onur_Ilgaz Palembang Bridges (APIO15_bridge) C++17
63 / 100
 2000 ms 9828 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

int solve(vector<pair<int,int> > v, int st, int nd) {
	if(st == nd) return 0;
	vector <int> p;
	int ans = 0;
	for(int i = st; i < nd; i++) {
		int a = v[i].first, b = v[i].second;
		// cout << a << " " << b << "\n";
		ans++;
		p.push_back(a);
		p.push_back(b);
	}
	sort(p.begin(), p.end());
	int bridge = p[p.size() / 2];
	for(auto it:p) {
		ans += abs(bridge-it);
	}
	// cout << "\n";
	return ans;
}

void solvek2(){
	fast
	int n;
	cin >> n;
	vector <pair<int, int> > p;
	int add_ans = 0;
	for(int i = 0; i < n; i++) {
		char fuck1, fuck2;
		int a, b;
		cin >> fuck1 >> a >> fuck2 >> b;
		if(fuck1 == fuck2) {
			add_ans += abs(a - b);
		}
		else {
			p.push_back({min(a, b), max(a, b)});
		}
	}
	sort(p.begin(), p.end(), [&](const pair<int,int>&a, const pair<int,int>&b) {
		return ((double)a.first + a.second) / 2 < ((double)b.first + b.second) / 2;
	});
	int m = p.size();
	if(m == 0) {
		cout << add_ans << "\n";
		return;
	}
	int ans = inf;
	for(int i = 0; i < m; i++) {
		int tans = solve(p, 0, i) + solve(p, i, m);
		ans = min(ans, tans);
		// cout << tans << "\n\n";
	}
	cout << ans + add_ans << "\n";
}

void solvek1() {
	int n;
	cin >> n;
	vector <int> p;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		char fuck1, fuck2;
		int a, b;
		cin >> fuck1 >> a >> fuck2 >> b;
		if(fuck1 == fuck2) {
			ans += abs(a - b);
		}
		else {
			ans += 1;
			p.push_back(a);
			p.push_back(b);
		}
	}
	sort(p.begin(), p.end());
	int bridge = p[p.size() / 2];
	for(auto it:p) {
		ans += abs(bridge-it);
	}
	cout << ans << "\n";
}

int32_t main() {
	fast
	int k;
	cin >> k;
	if(k == 1) {
		solvek1();
	}
	else {
		solvek2();
	}
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 16 ms 3368 KB Output is correct
13 Correct 32 ms 4312 KB Output is correct
14 Correct 23 ms 3796 KB Output is correct
15 Correct 23 ms 2740 KB Output is correct
16 Correct 18 ms 3796 KB Output is correct
17 Correct 22 ms 4444 KB Output is correct
18 Correct 26 ms 4052 KB Output is correct
19 Correct 30 ms 4308 KB Output is correct
20 Correct 21 ms 3804 KB Output is correct
21 Correct 27 ms 4056 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 18 ms 552 KB Output is correct
14 Correct 64 ms 528 KB Output is correct
15 Correct 74 ms 540 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 19 ms 524 KB Output is correct
18 Correct 10 ms 348 KB Output is correct
19 Correct 20 ms 564 KB Output is correct
20 Correct 24 ms 348 KB Output is correct
21 Correct 53 ms 536 KB Output is correct
22 Correct 26 ms 348 KB Output is correct
23 Correct 19 ms 568 KB Output is correct
24 Correct 27 ms 560 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 704 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 18 ms 348 KB Output is correct
14 Correct 65 ms 536 KB Output is correct
15 Correct 74 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 21 ms 524 KB Output is correct
18 Correct 10 ms 532 KB Output is correct
19 Correct 19 ms 348 KB Output is correct
20 Correct 23 ms 348 KB Output is correct
21 Correct 52 ms 348 KB Output is correct
22 Correct 24 ms 344 KB Output is correct
23 Correct 19 ms 348 KB Output is correct
24 Correct 24 ms 560 KB Output is correct
25 Execution timed out 2053 ms 9828 KB Time limit exceeded
26 Halted 0 ms 0 KB -