Submission #871331

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
871331	2023-11-10T15:08:07 Z	qthang2k11	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	95 ms	4472 KB

bridge

// [+] 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int N = 1e5 + 5;
 
int k, n;
ll ans = 0;
 
vector<pair<int, int>> arr;
ll pref[N], suf[N];
 
priority_queue<int> p1;
priority_queue<int, vector<int>, greater<int>> p2;
ll s1, s2;
 
void add(int x) {
	if (!p1.empty() && x < p1.top()) {
		p1.emplace(x);
		s1 += x;
	} else {
		p2.emplace(x);
		s2 += x;
	}
	
	while (p1.size() > p2.size()) {
		int val = p1.top();
		
		p1.pop();
		s1 -= val;
		
		p2.emplace(val);
		s2 += val;
	}
	
	while (p2.size() > p1.size()) {
		int val = p2.top();
		
		p2.pop();
		s2 -= val;
		
		p1.emplace(val);
		s1 += val;
	}
}
 
inline ll cost() {
	int med = p1.top();
	return (1LL * med * p1.size() - s1) + (s2 - 1LL * med * p2.size());
}
 
void calc(ll dp[], bool rev) {
	while (!p1.empty()) p1.pop();
	while (!p2.empty()) p2.pop();
	s1 = s2 = 0;
	
	int m = arr.size();
	
	for (int i = 1; i <= m; i++) {
		add(arr[i - 1].first);
		add(arr[i - 1].second);
		dp[i] = cost();
	}
	
	if (rev) {
		reverse(dp + 1, dp + m + 1);
	}
}
 
int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> k >> n;
	for (int i = 1; i <= n; i++) {
		char c1, c2;
		int p1, p2;
		cin >> c1 >> p1 >> c2 >> p2;
		if (c1 == c2) {
			ans += abs(p1 - p2);
		} else {
			arr.emplace_back(p1, p2);
		}
	}
	
	sort(arr.begin(), arr.end(), [&] (const pair<int, int> &x, const pair<int, int> &y) {
		return x.first + x.second < y.first + y.second;
	});
	
	calc(pref, false);
	reverse(arr.begin(), arr.end());
	calc(suf, true);
	
	if (k == 1) {
		ans += pref[arr.size()];
	} else {
		int m = arr.size();
		ll res = ans + pref[m];
		for (int i = 1; i < m; i++)
			res = min(res, ans + pref[i] + suf[i + 1]);
		ans = res;
	}
	
	cout << ans + arr.size();
	
	return 0;
}

Subtask #1
8.0 / 8.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	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 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	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct

Subtask #2
14.0 / 14.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	0 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	1 ms	344 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	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	30 ms	4068 KB	Output is correct
13	Correct	84 ms	4044 KB	Output is correct
14	Correct	71 ms	3784 KB	Output is correct
15	Correct	48 ms	2772 KB	Output is correct
16	Correct	37 ms	4472 KB	Output is correct
17	Correct	68 ms	3968 KB	Output is correct
18	Correct	68 ms	3936 KB	Output is correct
19	Correct	72 ms	4012 KB	Output is correct
20	Correct	40 ms	3788 KB	Output is correct
21	Correct	73 ms	4292 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	600 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	344 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	0 ms	600 KB	Output is correct
4	Correct	0 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	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	344 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct

Subtask #5
37.0 / 37.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	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	30 ms	3912 KB	Output is correct
26	Correct	65 ms	4308 KB	Output is correct
27	Correct	84 ms	4192 KB	Output is correct
28	Correct	95 ms	4268 KB	Output is correct
29	Correct	85 ms	4048 KB	Output is correct
30	Correct	43 ms	2252 KB	Output is correct
31	Correct	33 ms	4304 KB	Output is correct
32	Correct	69 ms	4000 KB	Output is correct
33	Correct	70 ms	4448 KB	Output is correct
34	Correct	71 ms	4040 KB	Output is correct
35	Correct	41 ms	4052 KB	Output is correct
36	Correct	69 ms	3920 KB	Output is correct
37	Correct	23 ms	4056 KB	Output is correct

Submission #871331

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