Submission #364609

#	Time	Username	Problem	Language	Result	Execution time	Memory
364609		Berted	Aliens (IOI16_aliens)	C++17	100 / 100	192 ms	8252 KiB

aliens

#include "aliens.h"

#include <iostream>
#include <algorithm>
#include <deque>

#define ll long long
#define ell __int128_t
#define pii pair<ll, ll>
#define fst first
#define snd second
#define ppi pair<pii, int>

const ll MN = -(ll)1e12 - 7, MX = 1;

using namespace std;

int N;
vector<pii> ivl;
deque<ppi> cht;
pii DP[100001];
ll Cs[100001];

inline bool validLine(const pii &l, const pii &m, const pii &r) 
{
	return (ell)(m.snd - l.snd) * (m.fst - r.fst) <= (ell)(r.snd - m.snd) * (l.fst - m.fst);
}
inline pii evalLine(const ppi &l, const int& x) {return {l.fst.fst * x + l.fst.snd, l.snd};}

inline pii solve(ll C)
{
	cht.push_back({{-2 * ivl[0].fst, ivl[0].fst * ivl[0].fst}, 0});
	for (int i = 0; i < N; i++)
	{
		while (cht.size() > 1 && evalLine(cht[0], ivl[i].snd) > evalLine(cht[1], ivl[i].snd)) {cht.pop_front();}
		pii temp = evalLine(cht[0], ivl[i].snd);
		DP[i] = {ivl[i].snd * ivl[i].snd + temp.fst - C, temp.snd + 1}; 

		if (i + 1 < N)
		{
			ppi tempLine = {{-2 * ivl[i + 1].fst, DP[i].fst - Cs[i] + ivl[i + 1].fst * ivl[i + 1].fst}, DP[i].snd};
			while (cht.size() > 1 && !validLine(cht[cht.size() - 2].fst, cht.back().fst, tempLine.fst)) {cht.pop_back();}
			cht.push_back(tempLine);
		}
		//cerr << "DP: " << i << ", " << DP[i].fst << " " << DP[i].snd << "\n"; 
	}
	cht.clear();
	return DP[N - 1];
}

inline void procIvl()
{
	vector<pii> temp;
	int L = ivl[0].fst, R = ivl[0].snd;
	for (const auto &x : ivl)
	{
		if (x.snd > R)
		{
			if (L != x.fst) {temp.push_back({L - 1, R});}
			L = x.fst, R = x.snd;
		}
	}
	temp.push_back({L - 1, R});

	//for (auto &x : temp) cerr << x.fst << " " << x.snd << "\n";

	swap(ivl, temp);
	N = ivl.size();
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) 
{
	for (int i = 0; i < n; i++)
	{
		ivl.push_back({min(r[i], c[i]), max(r[i], c[i])});
	}
	sort(ivl.begin(), ivl.end());

	procIvl();
	k = min(k, N);

	for (int i = 0; i + 1 < N; i++)
	{
		Cs[i] = max(0LL, ivl[i].snd - ivl[i + 1].fst);
		Cs[i] *= Cs[i];
		//cerr << "ISCT : " << i << ", " << Cs[i] << "\n";
	}

	ll L = MN, R = MX;
	while (L < R)
	{
		ll M = L + R >> 1; 
		//cerr << "BSR: " << M << "\n";
		pii res = solve(M);
		
		if (res.snd <= k) L = M + 1;
		else R = M;
	}

	pii res = solve(L - 1);
    return res.fst + (L - 1) * k;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |   ll M = L + R >> 1;
      |          ~~^~~

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