Submission #290229

#	Time	Username	Problem	Language	Result	Execution time	Memory
290229		amoo_safar	Aliens (IOI16_aliens)	C++17	25 / 100	101 ms	4856 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;

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

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


ll dp[N][K];
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]));
	}
}


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);
	ans = dp[m - 1][k];
	//for(int i = 1; i <= k; i++) ans = min(ans, dp[m - 1][i]);
	return ans;
}

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