Submission #256625

#	Time	Username	Problem	Language	Result	Execution time	Memory
256625		tinjyu	Aliens (IOI16_aliens)	C++14	4 / 100	73 ms	640 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
	int x,y;
}a[1000005];
long long int dp[50005][105],x[100005],y[100005];
bool cmp(node a,node b)
{
	if(a.x<b.x)return 1;
	if(a.x>b.x)return 0;
	if(a.y<a.y)return 1;
	return 0;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for(int i=0;i<n;i++)
    {
    	a[i].x=r[i];
    	a[i].y=c[i];
    	if(a[i].y<a[i].x)
    	{
    		swap(a[i].x,a[i].y);
		}
	}
	sort(a,a+n,cmp);
	long long int cnt=1;
	x[1]=a[0].x;
	y[1]=a[0].y;
	for(int i=1;i<n;i++)
	{
		if(a[i].x>x[cnt] && a[i].y>=y[cnt])
		{
			cnt++;
			x[cnt]=a[i].x;
			y[cnt]=a[i].y;
		}
		else if(a[i].x==x[cnt] && a[i].y>y[cnt])
		{
			x[cnt]=a[i].x;
			y[cnt]=a[i].y;
		}
	}
	n=cnt;
	x[0]=-1;
	y[0]=-1;
	for(int i=1;i<=n;i++)
	{
		//cout<<x[i]<<" "<<y[i]<<endl;
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=k;j++)dp[i][j]=99999999999999999;
	}
	dp[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			long long int nowy=y[i],nowx=x[i];
			for(int l=i;l>=1;l--)
			{
				nowx=x[l];
				if(y[l-1]-x[l]+1>0)dp[i][j]=min(dp[i][j],dp[l-1][j-1]+(nowy-nowx+1)*(nowy-nowx+1)-(y[l-1]-x[l]+1)*(y[l-1]-x[l]+1));
				else dp[i][j]=min(dp[i][j],dp[l-1][j-1]+(nowy-nowx+1)*(nowy-nowx+1));
				//cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<dp[l-1][j-1]<<" "<<nowx<<" "<<nowy<<endl;
			}
		}
	}
	long long int ans=10000000000000;
	for(int i=0;i<=k;i++)
	{
		ans=min(dp[n][i],ans);
	}
	return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'bool cmp(node, node)':
aliens.cpp:13:8: warning: self-comparison always evaluates to false [-Wtautological-compare]
  if(a.y<a.y)return 1;
     ~~~^~~~

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