Submission #32012

#	Time	Username	Problem	Language	Result	Execution time	Memory
32012		imeimi2000	Aliens (IOI16_aliens)	C++14	100 / 100	179 ms	8584 KiB

aliens

#include "aliens.h"
#include <algorithm>

using namespace std;
typedef long long llong;
typedef long double ld;

struct point {
	int x, y;
	bool operator<(const point &p) const {
		return x < p.x || (x == p.x && y > p.y);
	}
};

int n, m, k;
vector<point> _ps;
vector<point> ps;

llong sqr(int x) {
	return (llong)x * x;
}

struct line {
	int cnt;
	llong m, b;
} st[100000];
int top, bot;

void push(line x) {
	while (top > bot && (ld)(x.b - st[top].b) / (st[top].m - x.m)
		<= (ld)(st[top - 1].b - st[top].b) / (st[top].m - st[top - 1].m))
		--top;
	st[++top] = x;
}

llong func(line l, int x) {
	return l.m * x + l.b;
}

pair<int, llong> query(int x) {
	while (top > bot && func(st[bot + 1], x) <= func(st[bot], x)) ++bot;
	return { st[bot].cnt, func(st[bot], x) };
}

llong dp[100000];
int cnt[100000];
//dp[i] = min(dp[j] + x[j + 1] ^ 2 - 2 * x[j + 1] * y[i] + y[i] ^ 2 + cost);
int getPhoto(llong c) {
	top = -1; bot = 0;
	push({ 0, -2ll * ps[0].x, sqr(ps[0].x) });
	for (int i = 0; i < n; ++i) {
		auto ret = query(ps[i].y + 1);
		dp[i] = ret.second + sqr(ps[i].y + 1) + c;
		cnt[i] = ret.first + 1;
		if (i < n - 1)
			push({ cnt[i], -2ll * ps[i + 1].x, dp[i] + sqr(ps[i + 1].x) - sqr(max(0, ps[i].y - ps[i + 1].x + 1)) });
	}
	return cnt[n - 1];
}

long long take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c) {
	n = _n;
	m = _m;
	k = _k;
	_ps.reserve(n);
	ps.reserve(n);
	for (int i = 0; i < n; ++i) {
		_ps.push_back({ min(_r[i], _c[i]), max(_r[i], _c[i]) });
	}
	sort(_ps.begin(), _ps.end());
	for (point i : _ps) {
		if (ps.empty() || ps.back().x < i.x && ps.back().y < i.y)
			ps.push_back(i);
	}
	n = ps.size();
	k = min(n, k);
	llong s = 0ll, e = (llong)m * m;
	int l = -1, r = n + 1;
	llong lvalue, rvalue;
	while (s <= e) {
		llong m = (s + e) / 2;
		int ret = getPhoto(m);
		if (ret == k) return dp[n - 1] - ret * m;
		if (ret < k) {
			e = m - 1;
			if (l < ret) {
				l = ret; lvalue = dp[n - 1] - ret * m;
			}
		}
		else {
			s = m + 1;
			if (ret < r) {
				r = ret; rvalue = dp[n - 1] - ret * m;
			}
		}
	}
    return rvalue + ((lvalue - rvalue) / (r - l)) * (r - k);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:72:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if (ps.empty() || ps.back().x < i.x && ps.back().y < i.y)
                                       ^
aliens.cpp:97:30: warning: 'rvalue' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return rvalue + ((lvalue - rvalue) / (r - l)) * (r - k);
                              ^
aliens.cpp:97:30: warning: 'lvalue' may be used uninitialized in this function [-Wmaybe-uninitialized]

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