Submission #777928

#	Time	Username	Problem	Language	Result	Execution time	Memory
777928		said	Aliens (IOI16_aliens)	C++17	41 / 100	2079 ms	6312 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++)
	{
		dp[i] = INF;
			
		for (int w = 1; w <= i; w++)
		{
			long long aux = SQ(pts[i].Y - pts[w].X + 1ll) + dp[w - 1] - SQ(max(0ll, pts[w - 1].Y - pts[w].X + 1ll)) + C;
			
			if (dp[i] > aux)
			{
				dp[i] = aux; 
				qtd[i] = 1 + qtd[w - 1]; // Numero de quadrados usados
			}
		}
	}
	
	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;
	
		if (solve(n, mei) <= k) 
			fim = mei;
		else
			ini = mei + 1;
	}
	
	solve(n, ini);
	
	return dp[n] - k * ini;
}

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