Submission #119961

#	Time	Username	Problem	Language	Result	Execution time	Memory
119961		Lawliet	Aliens (IOI16_aliens)	C++14	0 / 100	3 ms	384 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"


#define X first
#define Y second
#define MAXK 110
#define MAXN 50010
#define INF 1000000000000000000LL

using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;

class ConvexHullTrick
{
	public:

		bool check(lli a, lli b, lli c, lli d)
		{
			if(a/b != c/d) return a/b >= c/d;

			a %= b; c %= d;

			if(a == 0 && c == 0) return true;
			if(a == 0 && c != 0) return false;
			if(c == 0) return true;//verificar essas condições

			return check(d , c , b , a);
		}

		void add(lli a, lli b)
		{
			while( sz > 2 && check(B[sz - 1] - B[sz] , A[sz] - A[sz - 1] , B[sz - 1] - b , a - A[sz - 1]))
			{
				A.pop_back();
				B.pop_back();

				sz--;
			}

			A.push_back( a );
			B.push_back( b );//sz = quantas retas tem

			sz++;
		}

		double iniLine(int i)
		{
			if(i == 0) return -INF;
			return (double (B[i - 1] - B[i]))/(A[i] - A[i - 1]);
		}

		lli query(lli x)
		{
			if(opt >= sz) opt = sz - 1;

			while(opt < sz - 1 && A[opt]*x + B[opt] >= A[opt + 1]*x + B[opt + 1])
				opt++; 

			return A[opt]*x + B[opt];
		}

		void clear()
		{
			A.clear();
			B.clear();

			sz = 0;
			opt = 0;
		}

	private:

		int sz;
		int opt;

		vector<lli> A, B;
};

lli N, M, K;

lli dp[MAXN][MAXK];

vector<pii> points;

ConvexHullTrick CHT;

void convertPoints()
{
	for(int g = 1 ; g <= N ; g++)
	{
		points[g].X++;
		points[g].Y = M - points[g].Y;
	}
}

void reflectPoints()
{
	for(int g = 1 ; g <= N ; g++)
	{
		if(points[g].X + points[g].Y < M + 1)
		{
			pii aux;
			aux.X = M + 1 - points[g].Y;
			aux.Y = M + 1 - points[g].X;

			points[g] = aux;
		}
	}
}

void makeParetto()
{
	sort(points.begin() , points.end());

	vector<pii> paretto;

	paretto.push_back({-INF , INF});
	paretto.push_back( points[1] );

	for(int g = 2 ; g <= N ; g++)
	{
		while( points[g].Y >= paretto.back().Y )
			paretto.pop_back();

		paretto.push_back( points[g] );
	} 

	points.clear();

	for(int g = 0 ; g < paretto.size() ; g++)
		points.push_back( paretto[g] );
}

void printPoints()
{
	for(int g = 1 ; g < points.size() ; g++)
		printf("(%lld ; %lld) ",points[g].X,points[g].Y);

	printf("\n");
}

long long int take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
	N = n; M = m; K = k;

	points.push_back({-1 , -1});

	for(int g = 0 ; g < n ; g++)
		points.push_back({c[g] , r[g]});

	convertPoints();

	//printPoints();

	reflectPoints();

	//printPoints();

	makeParetto();

	//printPoints();

	dp[0][0] = 0;

	for(int g = 1 ; g <= n ; g++)
		dp[g][0] = INF;

	for(int l = 1 ; l <= k ; l++)
	{
		CHT.clear();

		CHT.add( points[1].Y , - 2*M*points[1].Y + (points[1].Y * points[1].Y));
		//printf("BASE    %lld %lld\n",2*points[1].Y,points[1].Y*points[1].Y);

		for(int i = 1 ; i < points.size() ; i++)
		{
			lli out = (points[i].X * points[i].X);
			out -= 2*M*points[i].X;
			out += M*M;

			dp[i][l] = CHT.query( 2*points[i].X ) + out;

			//printf("query = %lld\n",CHT.query(2*points[i].X));
			//printf("dp(%d,%d) = %lld\n",i,l,dp[i][l]);

			if(i == points.size() - 1) continue;

			CHT.add( points[i + 1].Y , dp[i][l - 1] - 2*M*points[i + 1].Y + (points[i + 1].Y * points[i + 1].Y));
		}
	}

	return dp[points.size() - 1][K];
}

/*int main()
{
	int nn, mm, kk;
	int n1, n2;
	scanf("%d %d %d",&nn,&mm,&kk);

	vector<int> xx, yy;

	for(int g = 0 ; g < nn ; g++)
	{
		scanf("%d %d",&n1,&n2);

		xx.push_back(n1);
		yy.push_back(n2);
	}

	printf("%lld\n",take_photos(nn , mm , kk , xx , yy));
}*/

Compilation message (stderr)

aliens.cpp: In function 'void makeParetto()':
aliens.cpp:132:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < paretto.size() ; g++)
                  ~~^~~~~~~~~~~~~~~~
aliens.cpp: In function 'void printPoints()':
aliens.cpp:138:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 1 ; g < points.size() ; g++)
                  ~~^~~~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:177:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1 ; i < points.size() ; i++)
                   ~~^~~~~~~~~~~~~~~
aliens.cpp:188:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i == points.size() - 1) continue;
       ~~^~~~~~~~~~~~~~~~~~~~

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