Submission #79735

#	Time	Username	Problem	Language	Result	Execution time	Memory
79735		LeMans	Aliens (IOI16_aliens)	C++14	100 / 100	196 ms	48492 KiB

aliens

#include "aliens.h"
#include <stdio.h>
#include <bits/stdc++.h>
 
using namespace std;
 
typedef double db;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;
 
typedef pair < db, db > pdd;
typedef pair < db, ld > pdl;
typedef pair < ld, db > pld;
typedef pair < ld, ld > ldp;
 
typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;
 
#define F first
#define S second
 
#define en end()
#define bg begin()
 
#define rev reverse
#define mp make_pair
#define pb push_back
 
#define y1 y1234567890
#define um unordered_map
 
#define all(x) x.bg, x.en
#define sz(x) (int)x.size()
#define len(x) (int)strlen(x)
 
#define sqr(x) ((x + 0ll) * (x))
#define sqrd(x) ((x + 0.0) * (x))
 
#define forn(i, n) for (int i = 1; i <= n; i++)
 
const ll inf = (ll)1e18;
const ll mod = (ll)1e9 + 7;
 
const db eps = (db)1e-9;
const db pi = acos(-1.0);
 
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};
 
const int N = 100500;
 
ll dp[N];
pll a[N], line[N];
vector < pii > segs;
int n, m, lim, ptr, sz, cnt[N], f[N];
 
inline db cross(pll l1, pll l2) {
	return (l2.S - l1.S + 0.0) / (l1.F - l2.F);
}
 
inline void add(ll k, ll b, int cur) {
	while (sz >= 2) {
		if (cross(line[sz - 1], line[sz]) < cross(line[sz - 1], {k, b}))
			break;
		sz--;
	}
	line[++sz] = {k, b};
	cnt[sz] = cur;
	ptr = min(ptr, sz);
}

inline pll calc(ll C) {
	sz = 0;
	ptr = 1;

	memset(f, 0, sizeof(f));
	memset(cnt, 0, sizeof(cnt));

	for (int i = 1; i <= n; i++) {
		add(-2 * (a[i].F - 1), dp[i - 1] + sqr(a[i].F - 1) - (i - 1 > 0 ? sqr(max(0ll, a[i - 1].S - a[i].F + 1)) : 0), f[i - 1]);
		while (ptr < sz && cross(line[ptr], line[ptr + 1]) < a[i].S)
			ptr++;
		dp[i] = line[ptr].F * a[i].S + line[ptr].S + sqr(a[i].S) + C;
		f[i] = cnt[ptr] + 1;
	}

	return {dp[n], f[n]};
}

ll take_photos(int _n, int _m, int _lim, vector < int > x, vector < int > y) {
	n = _n;
	m = _m;
	lim = _lim;

	for (int i = 0; i < n; i++) {
		if (x[i] > y[i])
			swap(x[i], y[i]);
		segs.pb({x[i], -y[i]});
	}

	sort(all(segs));

	for (auto &i : segs)
		i.S = -i.S;

	n = 0;

	for (auto i : segs) {
		if (!n || a[n].S < i.S)
			a[++n] = i;
	}

	ll l = 0, r = (ll)1e12, ans = -1;

	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (calc(mid).S <= lim) {
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}

	assert(ans != -1);

	return calc(ans).F - lim * ans;
}

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