Submission #705536

#	Time	Username	Problem	Language	Result	Execution time	Memory
705536		600Mihnea	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2077 ms	5808 KiB

bridge

#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);
	}
	int sol = INF;
	for (int px = 0; px < (int)co.size(); px++)
	{
		for (int py = px + 1; py < (int)co.size(); py++)
		{
			for (int from = 0; from <= (int)values.size(); from += 2)
			{
				int cur = 0;
				for (int i = 0; i < from; i++)
				{
					cur += abs(values[i] - co[px]);
				}
				for (int i = from; i < (int)values.size(); i++)
				{
					cur += abs(values[i] - co[py]);
				}
				sol = min(sol, cur);
			}
		}
	}
	cout << sol + extra + n << "\n";
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37