Submission #703721

#	Time	Username	Problem	Language	Result	Execution time	Memory
703721		600Mihnea	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	500 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;
	assert(k == 1);
	{
		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;
	}
	set<int> scls;
	for (int i = 1; i <= n; i++)
	{
		scls.insert(c1[i].second);
		scls.insert(c2[i].second);
	}
	int best = INF;
	for (auto& x : scls)
	{
		int cur = 0;
		for (int i = 1; i <= n; i++)
		{
			cur += abs(x - c1[i].second) + abs(x - c2[i].second) + 1;
		}
		best = min(best, cur);
	}
	cout << best + extra << "\n";
	return 0;
}

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