Submission #986394

#	Time	Username	Problem	Language	Result	Execution time	Memory
986394		Pyqe	Aliens (IOI16_aliens)	C++17	100 / 100	154 ms	8756 KiB

aliens

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long ub=1e12;
long long nn=0,sl[100069],wg[100069],sk[100069];
pair<long long,long long> a[100069],dp[100069];

long long f(long long x,long long w)
{
	return sl[x]*w+wg[x];
}

bool cmp(long long x,long long y,long long x2,long long y2)
{
	return mp(x/y,x%y*y2)>mp(x2/y2,x2%y2*y);
}

bool chk(long long x,long long y,long long y2)
{
	return cmp(wg[x]-wg[y2],sl[y2]-sl[x],wg[x]-wg[y],sl[y]-sl[x]);
}

long long take_photos(int n,int m,int d,vector<int> ya,vector<int> xa)
{
	long long i,k,x,y,y2,sz,p,sm,c,lh,rh,md,zz,zm;
	
	for(i=1;i<=n;i++)
	{
		y=ya[i-1]+1;
		x=xa[i-1]+1;
		if(x<y)
		{
			swap(x,y);
		}
		y--;
		a[i]={x,-y};
	}
	sort(a+1,a+n+1);
	sz=n;
	n=0;
	for(i=1;i<=sz;i++)
	{
		x=a[i].fr;
		y=-a[i].sc;
		for(;n&&a[n].sc>=y;n--);
		n++;
		a[n]={x,y};
	}
	a[n+1].sc=m+1;
	for(lh=0,rh=ub;lh<=rh;)
	{
		md=(lh+rh)/2;
		nn=0;
		p=0;
		for(i=0;i<=n;i++)
		{
			x=a[i].fr;
			y=a[i].sc;
			y2=a[i+1].sc;
			if(i)
			{
				for(;p<nn&&(!p||f(sk[p+1],x)<f(sk[p],x));p++);
				dp[i]={f(sk[p],x)+x*x+md,dp[sk[p]].sc+1};
			}
			sl[i]=-y2*2;
			k=max(x-y2,0ll);
			wg[i]=dp[i].fr-k*k+y2*y2;
			for(;nn>=2&&chk(i,sk[nn],sk[nn-1]);nn--);
			p=min(p,nn);
			nn++;
			sk[nn]=i;
		}
		sm=dp[n].fr;
		c=dp[n].sc;
		if(c<=d)
		{
			zz=md;
			zm=sm;
			rh=md-1;
		}
		else
		{
			lh=md+1;
		}
	}
	return zm-zz*d;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:92:15: warning: 'zm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |  return zm-zz*d;
      |               ^
aliens.cpp:92:14: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |  return zm-zz*d;
      |            ~~^~

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