답안 #1034803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034803	2024-07-25T18:43:38 Z	Tob	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	557 ms	42884 KB

bridge

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7;

int n, k;
int l[N], r[N], l_[N], r_[N], ind[N];

int main () {
	FIO;
	cin >> k >> n;
	
	ll res = 0;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		char c1, c2;
		cin >> c1 >> a >> c2 >> b;
		if (c1 == c2) res += abs(a-b);
		else {
			res++;
			l_[cnt] = min(a, b);
			r_[cnt++] = max(a, b);
		}
	}
	for (int i = 0; i < cnt; i++) ind[i] = i;
	
	sort(ind, ind+cnt, [&](int x, int y) {return l_[x]+r_[x] < l_[y]+r_[y];});
	for (int i = 0; i < cnt; i++) l[i] = l_[ind[i]], r[i] = r_[ind[i]];
	
	if (k == 1) {
		multiset <int> s;
		ll d = -2*cnt, h = 0;
		for (int i = 0; i < cnt; i++) {
			s.insert(l[i]);
			s.insert(r[i]);
			h += l[i]+r[i];
		}
		for (int i = 0; i < cnt; i++) s.erase(--s.end());
		int la = 0;
		for (auto x : s) {
			h += d*(x-la);
			la = x;
			d += 2;
		}
		res += h;
	}
	else {
		set <pii> s;
		map <ll, ll> ma;
		ll y = -1, z = 0, h = 0;
		auto add = [&](ll x) {
			s.insert({x, ma[x]++});
			s.insert({x, ma[x]++});
			if (y == -1) {y = s.begin() -> F; return;}
			h += abs(y-x);
			auto p = s.find({y, z});
			if (x >= y) ++p;
			else --p;
			pii ny = *p;
			h -= max(0LL, ny.F-y);
			y = ny.F;
			z = ny.S;
		};
		vector <ll> pre(cnt+1, 0);
		for (int i = 0; i < cnt; i++) {
			add(l[i]);
			add(r[i]);
			pre[i+1] = h;
		}
		s.clear();
		ma.clear();
		y = -1; z = 0; h = 0;
		ll mn = pre[cnt];
		for (int i = cnt-1; i >= 0; i--) {
			add(l[i]);
			add(r[i]);
			mn = min(mn, pre[i]+h);
		}
		res += mn;
	}
	
	cout << res << "\n";

	return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	472 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	600 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	396 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 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	604 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	45 ms	12448 KB	Output is correct
13	Correct	76 ms	13908 KB	Output is correct
14	Correct	68 ms	11604 KB	Output is correct
15	Correct	41 ms	8276 KB	Output is correct
16	Correct	48 ms	13508 KB	Output is correct
17	Correct	51 ms	13904 KB	Output is correct
18	Correct	40 ms	13396 KB	Output is correct
19	Correct	57 ms	13992 KB	Output is correct
20	Correct	52 ms	13392 KB	Output is correct
21	Correct	54 ms	13648 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 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	0 ms	348 KB	Output is correct
6	Correct	0 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	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

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	600 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	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	352 KB	Output is correct
13	Correct	2 ms	600 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Correct	2 ms	860 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	2 ms	860 KB	Output is correct
21	Correct	2 ms	860 KB	Output is correct
22	Correct	1 ms	860 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	3 ms	860 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	464 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	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	344 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	604 KB	Output is correct
14	Correct	3 ms	604 KB	Output is correct
15	Correct	3 ms	860 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	868 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	776 KB	Output is correct
20	Correct	3 ms	860 KB	Output is correct
21	Correct	2 ms	860 KB	Output is correct
22	Correct	2 ms	856 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	2 ms	860 KB	Output is correct
25	Correct	216 ms	28768 KB	Output is correct
26	Correct	250 ms	29008 KB	Output is correct
27	Correct	500 ms	41044 KB	Output is correct
28	Correct	557 ms	42884 KB	Output is correct
29	Correct	502 ms	42832 KB	Output is correct
30	Correct	190 ms	22864 KB	Output is correct
31	Correct	190 ms	29656 KB	Output is correct
32	Correct	253 ms	42836 KB	Output is correct
33	Correct	222 ms	42576 KB	Output is correct
34	Correct	180 ms	42068 KB	Output is correct
35	Correct	189 ms	29776 KB	Output is correct
36	Correct	273 ms	42576 KB	Output is correct
37	Correct	185 ms	28968 KB	Output is correct

답안 #1034803

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