Submission #298915

#	Time	Username	Problem	Language	Result	Execution time	Memory
298915		SeDunion	Aliens (IOI16_aliens)	C++17	25 / 100	2016 ms	640 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int N = 4e3 + 123;
const int K = 4e3 + 123;
const ll INF = 1e18;

ll x[N], y[N];

ll sq (ll x) { return x * x; }

ll calc (int n, int m, int k) {
	k = min (n, k);
	vector<ll> dp(n + 1, INF), new_dp;
	for (int i = 1 ; i <= n ; ++ i) {
		dp[i] = sq(y[i] - x[1] + 1);
		//cout << dp[i] << " ";
	}
	//cout << "\n";
	for (int _ = 2 ; _ <= k ; ++ _) {
		new_dp = vector<ll>(n + 1, INF);
		for (int i = 1 ; i <= n ; ++ i) {
			for (int j = 2 ; j <= i ; ++ j) {
				new_dp[i] = min (new_dp[i], dp[j - 1] + sq(y[i] - x[j] + 1) - max (0ll, y[j - 1] - x[j] + 1) *
																						max (0ll, y[j - 1] - x[j] + 1));
			//	cout << "[" << new_dp[i] << " " << i << " " << j << "] ";
			}
			// cout << new_dp[i] << " ";
		}
		// cout << "\n";
		swap (dp, new_dp);
	}
	return dp[n];
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	vector<pair<int,int>> a(n);
	for (int i = 0 ; i < n ; ++ i) {
		if (r[i] > c[i]) swap (r[i], c[i]);
		a[i] = {r[i], c[i]};
	}
	sort (a.begin(), a.end());
	int n_ = 0;
	for (int i = 0, ymx = -1 ; i < n ; ++ i) {
		bool rm = false;
		//cout << a[i].first << " " << a[i].second << " a[i]\n";
		if (i + 1 < n && a[i].first == a[i + 1].first) {
			rm = true;
		}
		if (a[i].second <= ymx) {
			rm = true;
		}
		if (!rm) {
			++n_;
			x[n_] = a[i].first;
			y[n_] = a[i].second;
			//cout << x[n_] << " " << y[n_] << " {x,y}\n";
		}
		if (i + 1 > n || a[i].first != a[i + 1].first)
			ymx = max (ymx, a[i].second);
	}
	n = n_;
	return calc (n, m, k);
}

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