Submission #777951

#	Time	Username	Problem	Language	Result	Execution time	Memory
777951		said	Aliens (IOI16_aliens)	C++17	41 / 100	2064 ms	6088 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

#define N 100010
#define INF 1e18
#define SQ(x) ((x)*(x))

int qtd[N]; // Quantidade de retangulos usados pela PD
long long dp[N]; // PD

// Definindo a estrutura Ponto
#define X first
#define Y second
typedef pair<long long, long long> Ponto;

vector<Ponto> pts;

int solve(int n, long long C)
{
	// Casos bases da PD
	dp[0] = 0; qtd[0] = 0;
	
	// Execucao da PD
	for (int i = 1; i <= n; i++)
	{
		//printf("	i = %d\n", i);
		
		dp[i] = SQ(pts[i].Y + 1ll) + C;
			
		long long minimo = INF;
			
		for (int w = 1; w <= i; w++)
		{
			long long aux = -2ll*pts[w].X*pts[i].Y + SQ(pts[w].X) - 2ll*pts[w].X + dp[w - 1] - SQ(max(pts[w - 1].Y - pts[w].X + 1ll, 0ll));
						
			if (minimo > aux)
			{
				minimo = aux; 
				qtd[i] = 1 + qtd[w - 1]; // Numero de quadrados usados
			}
		}
		
		dp[i] += minimo;
	}
	
	return qtd[n]; // Retorna quantos quadrados foram usados
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
	// Ordenamos os pontos pela linha (desempate pela coluna)
	set<Ponto> pontos;
	
	for (int i = 0; i < n; i++)
		if (r[i] <= c[i]) 
			// Ponto acima ou dentro da diagonal principal
			pontos.insert({r[i], c[i]});
		else
			// Ponto abaixo da diagonal principal, entao espelhamos ele
			pontos.insert({c[i], r[i]}); 
	
	// Vector para armazenar os pontos que importam
	pts.push_back({-INF, -INF});
	
	// Selecionando apenas os pontos que realmente importam
	for (auto p : pontos)
	{
		Ponto ultimo = pts.back();
		if (ultimo.X == p.X) // Pontos na mesma linha
			pts[pts.size() - 1] = p;
		else if (ultimo.Y < p.Y) // Pontos em linha diferentes
				pts.push_back(p);
	}
	
	n = pts.size() - 1; // Atualizando o valor de n
	k = min(k, n); // Atualizando o valor de k
	
	// Busca binária no custo C
	long long ini = 0, fim = (long long) m * m;
	
	while (fim > ini)
	{
		long long mei = (ini + fim) / 2ll;
	
		//printf("ini = %d, mei = %d, fim = %d\n", ini, mei, fim);
	
		if (solve(n, mei) <= k) 
			fim = mei;
		else
			ini = mei + 1;
	}
	
	solve(n, ini);
	
	return dp[n] - k * ini;
}

/*
int main()
{
	freopen("116", "r", stdin);
	
	int n, m, k;
	cin >> n >> m >> k;
	
	vector<int> r, c;
	
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		
		r.push_back(x);
		c.push_back(y);
	}
	
	cout << take_photos(n, m, k, r, c) << '\n';
	
	return 0;
}
*/

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40