oj.uz

Submission #705542

# Submission time Handle Problem Language Result Execution time Memory
705542 2023-03-04T15:30:52 Z 600Mihnea Palembang Bridges (APIO15_bridge) C++17
63 / 100
 2000 ms 8672 KB 
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

#define int long long 

const int INF = (int)1e18 + 7;

pair<int, int> _rd_()
{
	string s;
	int i;
	cin >> s >> i;
	assert(s == "A" || s == "B");
	return { s == "B", i };
}

const int N = (int)1e5 + 7;
int k;
int n;
int extra;
pair<int, int> c1[N], c2[N];


signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	cin >> k >> n;
	{
		int y = 0;
		for (int i = 1; i <= n; i++)
		{
			c1[i] = _rd_();
			c2[i] = _rd_();
			if (c1[i].first == c2[i].first)
			{
				extra += abs(c1[i].second - c2[i].second);
				continue;
			}
			y++;
			c1[y] = c1[i];
			c2[y] = c2[i];
		}
		n = y;
	}
	if (n == 0)
	{
		cout << extra << "\n";
		return 0;
	}
	if (k == 1)
	{
		vector<int> coords;
		for (int i = 1; i <= n; i++)
		{
			coords.push_back(c1[i].second);
			coords.push_back(c2[i].second);
		}
		nth_element(coords.begin(), coords.begin() + n - 1, coords.end());
		int su = 0;
		for (int i = 0; i < 2 * n; i++)
		{
			su += abs(coords[i] - coords[n - 1]);
		}
		cout << su + extra + n << "\n";
		return 0;
	}
	assert(k == 2);
	set<int> s;
	for (int i = 1; i <= n; i++)
	{
		s.insert(c1[i].second);
		s.insert(c2[i].second);
		if (c1[i].second > c2[i].second)
		{
			swap(c1[i], c2[i]);
		}
	}
	vector<pair<int, int>> segs;
	for (int i = 1; i <= n; i++)
	{
		segs.push_back({ c1[i].second, c2[i].second });
		if (!(segs.back().first <= segs.back().second))
		{
			swap(segs.back().first, segs.back().second);
		}
		assert(segs.back().first <= segs.back().second);
	}
	sort(segs.begin(), segs.end(), [&](pair<int, int> a, pair<int, int> b) {return a.first + a.second < b.first + b.second; });
	vector<int> co;
	for (auto& x : s)
	{
		co.push_back(x);
	}
	assert(!co.empty());
	co.push_back(co.back());
	assert((int)co.size() >= 2);
	vector<int> values;
	for (int i = 0; i < (int)segs.size(); i++)
	{
		values.push_back(segs[i].first);
		values.push_back(segs[i].second);
	}
	vector<int> what((int)values.size() + 1, 0);
	int sol = INF;
	for (int from = 0; from <= (int)values.size(); from += 2)
	{
		int cur = 0;
		vector<int> keks;
		for (int i = 0; i < from; i++)
		{
			keks.push_back(values[i]);
		}
		if (!keks.empty())
		{
			sort(keks.begin(), keks.end());
			int mp = keks[(int)keks.size() / 2];
			for (auto& val : keks)
			{
				cur += abs(val - mp);
			}
		}
		what[from] += cur;
	}
	for (int from = (int)values.size(); from >= 0; from -= 2)
	{
		vector<int> keks;
		for (int i = from; i < (int)values.size(); i++)
		{
			keks.push_back(values[i]);
		}
		int cur = 0;
		if (!keks.empty())
		{
			sort(keks.begin(), keks.end());
			int mp = keks[(int)keks.size() / 2];
			for (auto& val : keks)
			{
				cur += abs(val - mp);
			}
		}
		sol = min(sol, what[from] + cur);
	}
	cout << sol + extra + n << "\n";
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 34 ms 5636 KB Output is correct
13 Correct 60 ms 5664 KB Output is correct
14 Correct 49 ms 5516 KB Output is correct
15 Correct 25 ms 3412 KB Output is correct
16 Correct 41 ms 5628 KB Output is correct
17 Correct 38 ms 5672 KB Output is correct
18 Correct 41 ms 5788 KB Output is correct
19 Correct 41 ms 5824 KB Output is correct
20 Correct 38 ms 5860 KB Output is correct
21 Correct 44 ms 5884 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 32 ms 440 KB Output is correct
14 Correct 82 ms 468 KB Output is correct
15 Correct 80 ms 468 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 21 ms 428 KB Output is correct
18 Correct 12 ms 440 KB Output is correct
19 Correct 24 ms 468 KB Output is correct
20 Correct 26 ms 588 KB Output is correct
21 Correct 62 ms 568 KB Output is correct
22 Correct 29 ms 468 KB Output is correct
23 Correct 25 ms 468 KB Output is correct
24 Correct 27 ms 580 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 224 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 25 ms 468 KB Output is correct
14 Correct 73 ms 456 KB Output is correct
15 Correct 82 ms 572 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 23 ms 412 KB Output is correct
18 Correct 12 ms 340 KB Output is correct
19 Correct 26 ms 464 KB Output is correct
20 Correct 26 ms 588 KB Output is correct
21 Correct 59 ms 468 KB Output is correct
22 Correct 27 ms 468 KB Output is correct
23 Correct 23 ms 468 KB Output is correct
24 Correct 26 ms 468 KB Output is correct
25 Execution timed out 2075 ms 8672 KB Time limit exceeded
26 Halted 0 ms 0 KB -