제출 #777923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777923		said	Aliens (IOI16_aliens)	C++17	컴파일 에러	0 ms	0 KiB

aliens

#include "aliens.h"
#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, mei) <= k) 
			fim = mei;
		else
			ini = mei + 1;
	}
	
	solve(n, ini);
	
	return dp[n] - k * ini;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccFEUzNA.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status