Submission #60096

#	Time	Username	Problem	Language	Result	Execution time	Memory
60096		TadijaSebez	Aliens (IOI16_aliens)	C++11	4 / 100	4 ms	724 KiB

aliens

#include "aliens.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
#define ldb long double
#define mp make_pair
#define pb push_back
const int N=100050;
const int M=1000050;
int x[N],y[N],n,m,k;
ldb dp[N];int cnt[N];
struct Line
{
	ldb k,n;
	int cnt;
	Line(){}
	Line(ldb a, ldb b, int c){ k=a,n=b,cnt=c;}
	ldb Get(ll x){ return k*x+n;}
	long double sec(Line b){ return (long double)(b.n-n)/(k-b.k);}
} cht[N];
int L=1,R;
void AddLine(Line t)
{
	while(R>L && cht[R].sec(t)<=cht[R-1].sec(cht[R])) R--;
	cht[++R]=t;
}
pair<ldb,int> Get(ll x)
{
	while(L<R && cht[L].Get(x)>=cht[L+1].Get(x)) L++;
	return mp(cht[L].Get(x),cht[L].cnt);
}
ll sec(int i, int j)
{
	ll ans=0;
	if(j==0) return 0;
	if(y[j]>=x[i]) ans=y[j]-x[i]+1;
	return ans*ans;
}
int Solve(ldb c)
{
	int i,j;L=1;R=0;
	for(i=1;i<=n;i++)
	{
		AddLine(Line(-2*x[i],(ll)x[i]*x[i]+dp[i-1]-sec(i,i-1),cnt[i-1]));
		pair<ldb,int> tmp=Get(y[i]+1);
		dp[i]=tmp.first+c+(ll)(y[i]+1)*(y[i]+1);
		cnt[i]=tmp.second+1;
		//printf("i:%i %lld %i\n",i,dp[i],cnt[i]);
	}
	return cnt[n];
}
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
bool comp(pair<int,int> a, pair<int,int> b){ return a.first<b.first || (a.first==b.first && a.second>b.second);}
ll take_photos(int _n, int _m, int _k, vector<int> _x, vector<int> _y)
{
	n=_n;m=_m;k=_k;
	int i,j;
	vector<pair<int,int> > tmp;
	for(i=0;i<n;i++) tmp.pb(mp(min(_x[i],_y[i]),max(_x[i],_y[i])));
	sort(tmp.begin(),tmp.end(),comp);
	n=0;int mr=-1;
	for(i=0;i<tmp.size();i++)
	{
		if(tmp[i].second>mr)
		{
			n++;
			x[n]=tmp[i].first;
			y[n]=tmp[i].second;
			//printf("(%i %i)\n",x[n],y[n]);
			mr=y[n];
		}
	}
	ldb bot=0,top=(ll)m*m,mid,ans;
	bool lf=0,rf=0;
	while(top-bot>=0.0000001)
	{
		mid=(top+bot)/2;
		//printf("mid:%i %i\n",mid,Solve(mid));
		if(Solve(mid)<=k) ans=mid,top=mid-1,lf=1;
		else bot=mid+1,rf=1;
	}
	//printf("->ans:%lld\n",ans);
	int h=Solve(ans);
	if(h!=k && lf && rf) return -1;
	return (ll)(dp[n]-ans*cnt[n]+0.5);
}
//--------------------------//
/*
int main()
{
	int n,m,k,i;
	scanf("%i %i %i",&n,&m,&k);
	vector<int> x,y;
	x.resize(n);y.resize(n);
	for(i=0;i<n;i++) scanf("%i %i",&x[i],&y[i]);
	printf("%lld\n",take_photos(n,m,k,x,y));
	return 0;
}
*/
//--------------------------//

Compilation message (stderr)

aliens.cpp: In function 'int Solve(long double)':
aliens.cpp:44:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;L=1;R=0;
        ^
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:66:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<tmp.size();i++)
          ~^~~~~~~~~~~
aliens.cpp:61:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
aliens.cpp:87:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int h=Solve(ans);
                 ^

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