Submission #135541

#	Time	Username	Problem	Language	Result	Execution time	Memory
135541		Mahdi_Jfri	Aliens (IOI16_aliens)	C++14	4 / 100	95 ms	94456 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;
const int maxk = 1e2 + 20;

int l[maxn] , r[maxn];

ll a[maxn] , b[maxn] , dp[maxn][maxk];

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[i] - a[j]);
}

void add(int i , int j)
{
	a[i] = -2 * l[i + 1];
	b[i] = dp[i][j - 1] + 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);
}

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

ll 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 f(hull[pt] , x);
}

long long take_photos(int n, int m, int k, vector<int> R, vector<int> C)
{
	m = m;
	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;
	memset(dp , 63 , sizeof dp);
	memset(dp[0] , 0 , sizeof dp[0]);

	for(int j = 1; j <= k; j++)
	{
		hull.clear();
		pt = 0;
		for(int i = 1; i <= n; i++)
		{
			add(i - 1 , j);
			dp[i][j] = get(r[i]) + t2(r[i]);
			//min(dp[i][j] , dp[lx][j - 1] + t2(l[lx + 1]) + t2(r[i]) - t2(max(0 , r[lx] - l[lx + 1])));
			// shib = l[lx + 1]
		}
	}

	return dp[n][k];
}

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