Submission #654231

#	Time	Username	Problem	Language	Result	Execution time	Memory
654231		jamezzz	Aliens (IOI16_aliens)	C++17	100 / 100	225 ms	6964 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pf printf
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define INF 1023456789
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<pair<ll,ll>,int> line;

#define maxn 100005

int n,cnt[maxn];
ll dp[maxn];
deque<line> dq;
vector<ii> pts,tmp;

inline ll sq(ll x){
	return x*x;
}

inline ld poi(line a,line b){
	auto[m1,c1]=a.fi;
	auto[m2,c2]=b.fi;
	return (ld)(c1-c2)/(m2-m1);
}

inline ll eval(line a,ll x){
	return a.fi.fi*x+a.fi.se;
}

int calc(ll cost){
	while(!dq.empty())dq.ppb();
	for(int i=1;i<n;++i){
		ll m=-2*(pts[i].fi-1);//always distinct
		ll c=dp[i-1]+cost+sq(pts[i].fi-1)-sq(max(0,pts[i-1].se-pts[i].fi+1));
		line l={{m,c},i-1};
		while(sz(dq)>=2&&poi(dq[sz(dq)-1],l)<=poi(dq[sz(dq)-1],dq[sz(dq)-2]))dq.ppb();
		dq.pb(l);
		while(sz(dq)>=2&&eval(dq[0],pts[i].se)>eval(dq[1],pts[i].se))dq.ppf();
		dp[i]=eval(dq[0],pts[i].se)+sq(pts[i].se);
		cnt[i]=cnt[dq[0].se]+1;
	}
	return cnt[n-1];
}

ll take_photos(int _n,int m,int k,vi r,vi c){
	n=_n;
	for(int i=0;i<n;++i){
		if(r[i]>c[i])swap(r[i],c[i]);
		tmp.pb({r[i],c[i]});
	}
	sort(all(tmp),[](ii &a,ii&b){
		if(a.fi==b.fi)return a.se>b.se;
		else return a.fi<b.fi;
	});
	pts.pb({-1,-1});
	for(int i=0;i<n;++i){
		if(pts.back().se<tmp[i].se)pts.pb(tmp[i]);
	}
	n=pts.size();
	ll lo=0,hi=1e12,mid,res=1e12;
	while(lo<=hi){
		mid=(lo+hi)>>1;
		if(calc(mid)<=k)res=mid,hi=mid-1;
		else lo=mid+1;
	}
	calc(res);
	return dp[n-1]-res*k;
}

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