Submission #290430

#	Time	Username	Problem	Language	Result	Execution time	Memory
290430		Saboon	Aliens (IOI16_aliens)	C++17	100 / 100	180 ms	8428 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, maxm = 1e6 + 5;
int n, m, k;
const ll inf = 1e18;
 
ll dp[maxm], pd[maxm];
 
vector<pair<int,int>> A;

ll SQ(ll x){return x*x;}


pair<ll,ll> Q[maxm];
int tail, head, P[maxm];

ll intersect(pair<ll,ll> fi, pair<ll,ll> se){
	return 1. * (se.second - fi.second) / (fi.first - se.first);
}

ll gety(pair<ll,ll> L, ll x){
	return L.first*x + L.second;
}

void addLine(ll a, ll b, int p){
	pair<ll,ll> L = {a,b};
	while (tail+2 <= head and intersect(Q[head-2],Q[head-1]) > intersect(Q[head-1],L))
		head --;
	Q[head] = L;
	P[head++] = p;
}

pair<ll,ll> get(ll x){
	while (tail+1 < head and gety(Q[tail],x) > gety(Q[tail+1],x))
		tail ++;
	ll ans = gety(Q[tail],x);
	int ted = maxn;
	for (int i = tail; i < head; i++){
		if (gety(Q[i],x) != ans)
			break;
		ted = min(ted, P[i]);
	}
	return {ans,ted};
}

pair<ll,ll> solve(ll x){
	tail = head = 0;
	int sz = A.size();
	for (int i = 0; i < sz; i++){
		if (i == 0)
			addLine(-2*A[i].first, SQ(A[i].first)+x, 1);
		else{
			ll P = max(0,A[i-1].second-A[i].first+1);
			addLine(-2*A[i].first, SQ(A[i].first)-P*P+dp[i-1]+x, pd[i-1]+1);
		}
		auto it = get(A[i].second+1);
		dp[i] = it.first + SQ(A[i].second+1);
		pd[i] = it.second;
	}
	return {dp[sz-1],pd[sz-1]};
}
 
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	::n = n, ::m = m, ::k = k;
	for (int i = 0; i < n; i++)
		if (r[i] > c[i])
			swap(r[i],c[i]);
	vector<pair<int,int>> Tmp;
	for (int i = 0; i < n; i++)
		Tmp.push_back({r[i],c[i]});
	sort(Tmp.begin(),Tmp.end());
	for (int i = 0; i < n; i++){
		if (!A.empty() and A.back().first == Tmp[i].first){
			A.pop_back();
			A.push_back(Tmp[i]);
		}
		else if (A.empty() or A.back().second < Tmp[i].second)
			A.push_back(Tmp[i]);
	}
	ll lo = -1, hi = 1e12 + 1;
	while (hi-lo > 1){
		ll mid = (lo+hi) >> 1;
		if (solve(mid).second > k)
			lo = mid;
		else
			hi = mid;
	}
	auto it = solve(hi);
	return it.first - hi*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