Submission #290259

#	Time	Username	Problem	Language	Result	Execution time	Memory
290259		amoo_safar	Aliens (IOI16_aliens)	C++17	41 / 100	1133 ms	4588 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 = 4e3 + 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]));
	}
}
*/
pll CheckN2(ll cost){

	fill(dp, dp + N , pll(Inf, Inf));
	dp[0] = {(C[0] - R[0]) * (C[0] - R[0]) + cost, 1};
	for(int i = 1; i < m; i++){
		for(int la = 1; la <= i; la ++){
			dp[i] = min(dp[i], {dp[la - 1].F - Dup[la] + (C[i] - R[la]) * (C[i] - R[la]) + cost, dp[la - 1].S + 1});
		}
		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: 0 / 19
• Subtask 6: 0 / 40