Submission #777920

#	Time	Username	Problem	Language	Result	Execution time	Memory
777920		said	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 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, int* r, 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, pts, mei) <= k) 
			fim = mei;
		else
			ini = mei + 1;
	}
	
	solve(n, pts, ini);
	
	return dp[n] - k * ini;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, int*, int*)':
aliens.cpp:80:16: error: cannot convert 'std::vector<std::pair<long long int, long long int> >' to 'long long int'
   80 |   if (solve(n, pts, mei) <= k)
      |                ^~~
      |                |
      |                std::vector<std::pair<long long int, long long int> >
aliens.cpp:19:28: note:   initializing argument 2 of 'int solve(int, long long int)'
   19 | int solve(int n, long long C)
      |                  ~~~~~~~~~~^
aliens.cpp:86:11: error: cannot convert 'std::vector<std::pair<long long int, long long int> >' to 'long long int'
   86 |  solve(n, pts, ini);
      |           ^~~
      |           |
      |           std::vector<std::pair<long long int, long long int> >
aliens.cpp:19:28: note:   initializing argument 2 of 'int solve(int, long long int)'
   19 | int solve(int n, long long C)
      |                  ~~~~~~~~~~^