Submission #1023111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023111		AmirAli_H1	Aliens (IOI16_aliens)	C++17	0 / 100	30 ms	48784 KiB

aliens

// In the name of Allah

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 4;
const int maxs = 2e6 + 4;
const ll oo = 1e18 + 4;

int n, m, k;
pii a[maxn]; vector<pii> A;
vector<int> ls[maxs];
priority_queue<pair<int, pii>> qu;
ll dp[2][maxn];

ll cal(pll a, pll b) {
	ll d = max(0ll, (a.F + a.S) - (b.F - b.S));
	return (4 * b.S * b.S - d * d);
}

bool upd(int r, int i, int j) {
	ll valx = oo;
	if (i == j) valx = dp[(r - 1) & 1][j];
	else {
		ll x1 = A[j + 1].F - A[j + 1].S, x2 = A[i].F + A[i].S;
		ll d = (x1 - x2) / 2; pll x = Mp(x1 + d, d);
		valx = dp[(r - 1) & 1][j] + cal(A[j], x);
	}
	
	if (valx < dp[r & 1][i]) {
		dp[r & 1][i] = valx;
		return 1;
	}
	return 0;
}

void solve(int ind, int l, int r, int lx, int rx) {
	if (r - l <= 0) return ;
	
	int mid = (l + r) / 2;
	int i = mid, k = -1;
	for (int j = lx; j < min(rx, i + 1); j++) {
		if (upd(ind, i, j)) k = j;
	}
	solve(ind, l, mid, lx, k + 1); solve(ind, mid + 1, r, k, rx);
}

ll take_photos(int Nx, int Mx, int Kx, vector<int> r, vector<int> c) {
	n = Nx; m = Mx; k = Kx;
	for (int i = 0; i < n; i++) {
		if (c[i] > r[i]) swap(c[i], r[i]);
		a[i] = Mp(r[i], c[i]);
		ls[a[i].F].pb(i);
	}
	
	A.pb(Mp(0, 0));
	for (int i = m - 1; i >= 0; i--) {
		for (int j : ls[i]) {
			qu.push(Mp(-a[j].S, Mp(i, j)));
		}
		for (int j : ls[i]) {
			if (qu.top().S.S == j) {
				int x1 = a[j].F, y1 = a[j].S;
				A.pb(Mp(x1 + y1 + 1, x1 - y1 + 1));
			}
		}
	}
	
	n = len(A); sort(all(A));
	for (int i = 0; i < n; i++) {
		if (i == 0) dp[0][i] = 0;
		else dp[0][i] = oo;
	}
	
	for (int r = 1; r <= k; r++) {
		for (int i = 0; i < n; i++) dp[r & 1][i] = dp[(r - 1) & 1][i];
		solve(r, 0, n, 0, n);
	}
	
	return dp[k & 1][n - 1] / 4;
}

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