Submission #60161

#	Time	Username	Problem	Language	Result	Execution time	Memory
60161		TadijaSebez	Aliens (IOI16_aliens)	C++11	100 / 100	365 ms	65772 KiB

aliens

#include "aliens.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=100050;
const int M=1000050;
int x[N],y[N],n,m,k;
ll dp[N];int cnt[N];
struct Line
{
	ll k,n;
	int cnt;
	Line(){}
	Line(ll a, ll b, int c){ k=a,n=b,cnt=c;}
	ll Get(ll x){ return k*x+n;}
};
struct cht
{
	deque<Line> hull;
	cht(){}
	void init(){ while(hull.size()) hull.pop_back();}
	bool bad(Line a, Line b, Line c)
	{
		return (a.n-b.n)*(c.k-a.k)>=(a.n-c.n)*(b.k-a.k);
	}
	void AddLine(Line t)
	{
		while(hull.size()>1 && bad(hull[hull.size()-2],hull[hull.size()-1],t)) hull.pop_back();
		hull.push_back(t);
	}
	pair<ll,int> Get(ll x)
	{
		while(hull.size()>1 && hull[0].Get(x)>hull[1].Get(x)) hull.pop_front();
		return mp(hull[0].Get(x),hull[0].cnt);
	}
} Hull;
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(ll c)
{
	int i;Hull.init();
	for(i=1;i<=n;i++)
	{
		Hull.AddLine(Line(-2*x[i],(ll)x[i]*x[i]+dp[i-1]-sec(i,i-1),cnt[i-1]));
		pair<ll,int> tmp=Hull.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(n==0 || (tmp[i].first>x[n] && tmp[i].second>y[n]))
		{
			n++;
			x[n]=tmp[i].first;
			y[n]=tmp[i].second;
			//printf("(%i %i)\n",x[n],y[n]);
			mr=y[n];
		}
	}
	ll bot=0,top=(ll)m*m,mid,ans=0;
	bool lf=0,rf=0;
	while(top>=bot)
	{
		mid=(top+bot)/2;
		//printf("mid:%i %i\n",mid,Solve(mid));
		if(Solve(mid)<=k) top=mid-1,lf=1;
		else bot=mid+1,rf=1,ans=mid+1;
	}
	//printf("->ans:%lld\n",ans);
	int h=Solve(ans);
	//if(h!=k && lf && rf) return -1;
	return dp[n]-ans*k;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:73:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<tmp.size();i++)
          ~^~~~~~~~~~~
aliens.cpp:68:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
aliens.cpp:72:10: warning: variable 'mr' set but not used [-Wunused-but-set-variable]
  n=0;int mr=-1;
          ^~
aliens.cpp:85:7: warning: variable 'lf' set but not used [-Wunused-but-set-variable]
  bool lf=0,rf=0;
       ^~
aliens.cpp:85:12: warning: variable 'rf' set but not used [-Wunused-but-set-variable]
  bool lf=0,rf=0;
            ^~
aliens.cpp:94:6: warning: unused variable 'h' [-Wunused-variable]
  int h=Solve(ans);
      ^

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