Submission #1136356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136356		raspy	Aliens (IOI16_aliens)	C++20	100 / 100	138 ms	10548 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

const int64_t inf = 10e10;

struct line
{
	int64_t c, m;
	line(int64_t _c, int64_t _m) {c = _c;m=_m;}
	int64_t operator()(int64_t x)
	{
		return c+m*x;
	}
	bool inter_ear(line l, line l1)
	{
		return (double)(c-l1.c)/(l1.m-m) < (double)(c-l.c)/(l.m-m);
	}
};

struct CHT
{
	deque<line> dq;
	deque<int64_t> pr;
	CHT() {dq = deque<line>();pr=deque<int64_t>();}
	void add(line l, int64_t k)
	{
		while (dq.size() > 1 && dq[dq.size()-2].inter_ear(dq.back(), l))
		{
			dq.pop_back();
			pr.pop_back();
		}
		dq.push_back(l);
		pr.push_back(k);
	}
	pair<int64_t, int64_t> get_best(int64_t x)
	{
		while (dq.size() > 1 && dq[1](x) < dq[0](x))
		{
			dq.pop_front();
			pr.pop_front();
		}
		return {dq[0](x), pr[0]};
	}
};

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

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
	// get rid of unimportant points
	vector<pair<int64_t, int64_t>> pnts(n); // array of points only below the line x=y
	for (int64_t i = 0; i < n; i++)
		pnts[i] = {min(r[i], c[i]), max(r[i], c[i])};
	sort((pnts).begin(), pnts.end(), [](pair<int64_t, int64_t> pr, pair<int64_t, int64_t> dr){
		if (pr.first == dr.first) return pr.second > dr.second;
		return pr.first < dr.first;
	}); // sort them by increasing row and decreasing column nummber
	vector<pair<int64_t, int64_t>> a; // save only important points
	a.push_back(pnts[0]);
	for (int64_t i = 1; i < n; i++)
		if (a.back().second < pnts[i].second)
			a.push_back(pnts[i]);
	//lambda optimization
	int64_t l = -1, d = 1e13;
	CHT ch;
	vector<pair<int64_t, int64_t>> dp;
	while (l+1 < d)
	{
		int64_t lamb = (l+d)/2;
		ch = CHT();
		dp = vector<pair<int64_t, int64_t>>(a.size());
		ch.add(line(sq(a[0].first)-2*a[0].first+1+lamb, -2*a[0].first), 0);
		for (int64_t i = 0; i < a.size(); i++)
		{
			auto [x, tk] = ch.get_best(a[i].second);
			x+=sq(a[i].second)+2*a[i].second;
			dp[i] = {x, tk+1};
			if (i==n-1) break;
			ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
		}
		if (dp.back().second <= k)
			d = lamb;
		else
			l = lamb;
	}
	int64_t lamb = d;
	ch = CHT();
	dp = vector<pair<int64_t, int64_t>>(a.size());
	ch.add(line(sq(a[0].first-1)+lamb, -2*a[0].first), 0);
	for (int64_t i = 0; i < a.size(); i++)
	{
		auto [x, tk] = ch.get_best(a[i].second);
		x+=sq(a[i].second)+2*a[i].second;
		dp[i] = {x, tk+1};
		if (i==n-1) break;
		ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
	}
	return dp.back().first-d*k;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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