Submission #290286

#	Time	Username	Problem	Language	Result	Execution time	Memory
290286		amoo_safar	Aliens (IOI16_aliens)	C++17	100 / 100	325 ms	10464 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n';

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll Inf = 1e18;
const int N = 1e5 + 10;
const int K = N;

vector<ll> R, C;
int n, m, k;


pll dp[N];
ll Dup[N];
void Prep(){
	ll r, c;
	for(int i = 1; i < m; i++){
		r = R[i]; c = C[i - 1];
		if(c > r)
			Dup[i] = (c - r) * (c - r);
	}
	//debug(Dup[1]);
}
/*
void SolveN2K(){
	memset(dp, 31, sizeof dp);
	dp[0][1] = (C[0] - R[0]) * (C[0] - R[0]);
	for(int i = 1; i < m; i++){
		for(int j = 1; j <= i + 1; j++){
			for(int la = 1; la <= i; la ++){
				dp[i][j] = min(dp[i][j], dp[la - 1][j - 1] - Dup[la] + (C[i] - R[la]) * (C[i] - R[la]));
			}
		}
		dp[i][1] = min(dp[i][1], (C[i] - R[0]) * (C[i] - R[0]));
	}
}
*/
//dp[i] = min(dp[i], {(dp[la - 1].F - Dup[la] + R[la] * R[la]) + (2*C[i] * (-R[la])) + (cost + C[i] * C[i]), dp[la - 1].S + 1});

typedef pair<ll, pair<pll, ll> > cht;

vector<cht> V;

ll Intersect(pll L1, pll L2, bool flg){
	ll d = L2.S - L1.S;
	ll M = L1.F - L2.F;
	if(d % M == 0){
		return d / M + (flg);
	} else {
		return d / M + (d >= 0);
	}
}

void Add(pll Ln, ll cnt){
	ll tmp;
	while(!V.empty()){
		tmp = Intersect(V.back().S.F, Ln, V.back().S.S <= cnt);
		if(tmp <= V.back().F) V.pop_back();
		else break;
	}
	tmp = -Inf;
	if(!V.empty())
		tmp = Intersect(V.back().S.F, Ln, V.back().S.S <= cnt);
	V.pb({tmp, {Ln, cnt}});
}

pll Get(ll p){
	assert(!V.empty());
	auto it = upper_bound(all(V), cht(p, {{Inf, Inf}, Inf}));
	it --;
	return {it -> S.F.S + p * it->S.F.F,it -> S.S};
}

pll CheckN2(ll cost){
	V.clear();
	fill(dp, dp + N , pll(Inf, Inf));
	dp[0] = {(C[0] - R[0]) * (C[0] - R[0]) + cost, 1};
	
	//Add({-R[i], dp[i - 1].F - Dup[i] + R[i] * R[i]}, dp[i - 1].S);
	for(int i = 1; i < m; i++){
		Add({-R[i], dp[i - 1].F - Dup[i] + R[i] * R[i]}, dp[i - 1].S);

		pll res = Get(2 * C[i]);
		res.F += cost + C[i] * C[i];
		res.S ++;
		//for(int la = 1; la <= i; la ++){
		//	dp[i] = min(dp[i], {(dp[la - 1].F - Dup[la] + R[la] * R[la]) + (2*C[i] * (-R[la])) + (cost + C[i] * C[i]), dp[la - 1].S + 1});
		//}
		dp[i] = res;
		dp[i] = min(dp[i], {(C[i] - R[0]) * (C[i] - R[0]) + cost, 1});
	}
	return dp[m - 1];
}

ll SolveN2LG(){
	if(k == 1){
		return (C[m - 1] - R[0]) * (C[m - 1] - R[0]);
	}
	if(k == m){
		ll ans = 0;
		for(int i = 0; i < m; i++){
			ans += (C[i] - R[i]) * (C[i] - R[i]) - Dup[i];
		}
		return ans;
	}

	ll L = 0, R = 1e12, mid;
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(CheckN2(mid).S <= k) R = mid;
		else L = mid;
	}
	pll res = CheckN2(R);
	//pll res2 = CheckN2(L);
	//if(res2.S == k)
		//return res2.F - res2.S * L;
	ll ans = res.F - res.S * R;
	ans -= R * (k - res.S);
	return ans;
}

ll take_photos(int _m, int _n, int _k, vector<int> _r, vector<int> _c) {
	n = _n; k = _k;

	for(int i = 0; i < _m; i++)
		if(_r[i] > _c[i])
			swap(_r[i], _c[i]);
	
	vector<int> I(_m);
	iota(all(I), 0);
	sort(all(I), [&](int i, int j){
		return pii(_r[i], -_c[i]) < pii(_r[j], -_c[j]);
	});
	int mx = -1;
	for(int i : I){
		if(_c[i] > mx){
			mx = _c[i];
			R.pb(_r[i]);
			C.pb(_c[i] + 1);
		}
	}
	m = R.size();
	
	ll ans = Inf;
	
	//cerr << "! " << m << '\n';
	//for(int i = 0; i < m; i++) cerr << R[i] << ' ' << C[i] << '\n';
	
	Prep();
	//SolveN2K();
	k = min(k, m);
	//for(int i = 1; i <= k; i++) ans = min(ans, dp[m - 1][i]);
	ans = SolveN2LG();
	return 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