Cod sursa(job #2652649)

Utilizator IRadu1529Radu Ionescu IRadu1529 Data 25 septembrie 2020 13:38:12
Problema Oite Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <fstream>
#include <unordered_map>
using namespace std;

ifstream fin("oite.in");
ofstream fout("oite.out");

int l, n, ans;

vector<int> o(1025);

unordered_map<int, vector<pair<int, int>>> map;

unordered_map<int, int> cnt;

int main()
{
	fin >> n >> l;

	for (int i = 1; i <= n; ++i)
	{
		fin >> o[i];

		cnt[o[i]]++;
	}

	sort(o.begin(), o.begin() + n);

	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j)
		{
			int s = o[i] + o[j];

			pair<int, int> p;

			p.first = o[i];  p.second = o[j];

			const auto& search = map.find(s);

			int c = 0;

			if (search != map.end())
				for (const auto& value : search->second)
					if (value.first == p.first || value.first == p.second)
					{
						c = 1;

						break;
					}

			if (c == 0)
				map[s].push_back(p);
		}

	for (auto i = map.begin(); i != map.end(); i++)
	{
		const auto& search1 = map.find(i->first);

		const auto& search2 = map.find(l - i->first);

		if (search1 == map.end() || search2 == map.end())
			continue;

		for (const auto& value : search1->second)
			for (const auto& value2 : search2->second)
			{
				int a = cnt[value.first], b = cnt[value.second], c = cnt[value2.first], d = cnt[value2.second];

				int m = min(a, min(b, min(c, d)));

				if (m > 0)
				{
					ans += m;

					cnt[value.first] -= m; cnt[value.second] -= m; cnt[value2.first] -= m; cnt[value2.second] -= m;
				}
			}
	}

	fout << ans;
}