Submission #160773

#	Time	Username	Problem	Language	Result	Execution time	Memory
160773		sofhiasouza	Cover (COCI18_cover)	C++14	24 / 120	99 ms	504 KiB

cover

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e3+10, inf = 1e9;

int n, x[maxn], y[maxn], comp[maxn], xc[maxn], yc[maxn], peso[maxn];
int total, maiorx, maiory;

int find(int x)
{
	if(comp[x] == x) return x;
	return comp[x] = find(comp[x]);
}

void join(int a, int b)
{
	a = find(a);
	b = find(b);

	if(peso[a] < peso[b]) swap(a, b);

	comp[b] = a;
	peso[a] += peso[b];
}

int main()
{
	cin >> n;

	for(int i = 1 ; i <= n ; i++)
	{
		cin >> x[i] >> y[i];
		comp[i] = i;
		peso[i] = 1;
		xc[i] = abs(x[i]+x[i]);
		yc[i] = abs(y[i]+y[i]);
		total += xc[i]*yc[i];
		maiorx = max(maiorx, abs(xc[i]));
		maiory = max(maiory, abs(yc[i]));
	}

	int flag1 = 0, flag2 = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		int area = xc[comp[i]]*yc[comp[i]];
		int melhor = inf, id = -1;

		for(int j = 1 ; j <= n ; j++)
		{
			if(comp[i] == comp[j]) continue;

			if(xc[i] == maiorx and !flag1 and yc[i] != maiory) continue;
			if(yc[i] == maiory and !flag2 and xc[i] != maiorx) continue;

			int areat = xc[comp[j]]*yc[comp[j]];
			int auxx = max(xc[comp[i]], xc[comp[j]]);
			int auxy = max(yc[comp[i]], yc[comp[j]]);

			int areap = auxx*auxy;
			int aumentou = areap-areat;

			if(aumentou < area and aumentou < melhor)
			{
				melhor = aumentou;
				id = j;
			}
		}

		if(xc[i] == maiorx and !flag1)
		{
			flag1 = 1;
		}

		if(yc[i] == maiory and !flag2)
		{
			flag2 = 1;
		}

		if(id != -1)
		{
			total -= area;
			total -= xc[comp[id]]*yc[comp[id]];
			xc[comp[i]] = max(xc[comp[i]], xc[comp[id]]);
			yc[comp[i]] = max(yc[comp[i]], yc[comp[id]]);
			xc[comp[id]] = max(xc[comp[i]], xc[comp[id]]);
			yc[comp[id]] = max(yc[comp[i]], yc[comp[id]]);
			join(id, i);
			total += xc[comp[i]]*yc[comp[i]];
		}
	}

	//for(int i = 1 ; i <= n ; i++) cout << i << ' ' << comp[i] << "\n";

	cout << total << "\n";	
}

• Subtask 1: 24 / 120