Submission #135685

#	Time	Username	Problem	Language	Result	Execution time	Memory
135685		Mahdi_Jfri	Aliens (IOI16_aliens)	C++14	4 / 100	10 ms	764 KiB

aliens

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

using namespace std;

#define ll long long
#define pb push_back
#define ld long double

const int maxn = 1e5 + 20;

int l[maxn] , r[maxn] , cnt[maxn] , k , n , par[maxn];

ld a[maxn] , b[maxn] , dp[maxn];

ll t2(int x)
{
	return 1LL * x * x;
}

vector<int> hull;
int pt;

ld IS(int i , int j)
{
	return (b[i] - b[j]) / (ld)(a[j] - a[i]);
}

void add(int i)
{
	a[i] = -2 * l[i + 1];
	b[i] = dp[i] + t2(l[i + 1]) - t2(max(0 , r[i] - l[i + 1]));

	int sz = hull.size();
	while(sz > 1 && IS(hull[sz - 2] , hull[sz - 1]) >= IS(hull[sz - 1] , i))
	{
		hull.pop_back();
		sz--;
	}

	hull.pb(i);
}

ld f(int ind , int x)
{
	return a[ind] * x + b[ind];
}

int get(int x)
{
	if(pt >= (int)hull.size())
		pt = (int)hull.size() - 1;
	while(pt + 1 < (int)hull.size() && f(hull[pt] , x) >= f(hull[pt + 1] , x))
		pt++;

	return hull[pt];
}

int check(ld x)
{
	memset(cnt , 0 , sizeof cnt);
	dp[0] = 0;
	hull.clear();
	for(int i = 1; i <= n; i++)
	{
		add(i - 1);
		int ind = get(r[i]);
		par[i] = ind;
		dp[i] = f(ind , r[i]) + t2(r[i]) + x;
		cnt[i] = cnt[ind] + 1;
	}

	return cnt[n]; 
}

long long take_photos(int N, int m, int K, vector<int> R, vector<int> C)
{
	m = m;
	k = K;
	n = N;
	vector<pair<int , int> > tmp;
	for(int i = 0; i < n; i++)
	{
		l[i] = min(R[i] , C[i]) , r[i] = max(R[i] , C[i]);
		tmp.pb({r[i] , -l[i]});
	}

	sort(tmp.begin() , tmp.end());
	for(int i = 0; i < n; i++)
	{
		l[i] = -tmp[i].second;
		r[i] = tmp[i].first;
	}
	tmp.clear();

	int mn = 1e9;
	for(int i = n - 1; i >= 0; i--)
		if(mn > l[i])
		{
			mn = l[i];
			tmp.pb({l[i] , r[i]});
		}

	reverse(tmp.begin() , tmp.end());
	n = tmp.size();
	for(int i = 1; i <= n; i++)
		l[i] = tmp[i - 1].first , r[i] = tmp[i - 1].second + 1;

	r[0] = l[0] = -1;

	if(k > n)
	{
		check(0);
		return dp[n];
	}
	ld lx = -1e18 , rx = 1e18;
	for(int _ = 0; _ < 200; _++)
	{
		ld mx = (lx + rx) / 2;
		int tmp = check(mx);
		if(tmp == k)
		{
			ll tmp = ceil(dp[n] - cnt[n] * mx);
			return tmp;
		}
		if(tmp <= k)
			rx = mx;
		else
			lx = mx;
	}

	check(rx);
	return dp[n] - cnt[n] * rx;
}

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