Submission #1023100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023100		AmirAli_H1	Aliens (IOI16_aliens)	C++17	25 / 100	2051 ms	49168 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);
}

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 j = 0; j <= k; j++) {
		for (int i = 0; i < n; i++) {
			if (i == 0) dp[j & 1][i] = 0;
			else if (j == 0) dp[j & 1][i] = oo;
			else {
				dp[j & 1][i] = dp[(j - 1) & 1][i];
				for (int r = 0; r < i; r++) {
					ll x1 = A[r + 1].F - A[r + 1].S, x2 = A[i].F + A[i].S;
					ll d = (x1 - x2) / 2; pll x = Mp(x1 + d, d);
					dp[j & 1][i] = min(dp[j & 1][i], dp[(j - 1) & 1][r] + cal(A[r], x));
				}
			}
		}
	}
	
	return dp[k & 1][n - 1] / 4;
}

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