Submission #794435

#	Time	Username	Problem	Language	Result	Execution time	Memory
794435		prvocislo	Aliens (IOI16_aliens)	C++17	100 / 100	794 ms	15400 KiB

aliens

#pragma once
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

struct seg
{
	int l, r;
};
bool cmp(seg a, seg b)
{
	if (a.l == b.l) return a.r > b.r;
	return a.l < b.l;
}
void upd(ll& a, ll b)
{
	a = min(a, b);
}
ll sq(ll x)
{
	return x * x;
}
struct line
{
	ld a, b; // a x + b
	int val;
	ld eval(ld x) { return a * x + b; }
};
ld inter(line a, line b) // prvy moment ked b zacne byt mensia ako a (b ma mensi slope inak)
{
	// b.a * x + b.b < a.a * x + a.b      ->      x < (a.b - b.b) / (b.a - a.a)
	if (abs(b.a - a.a) < 1e-9) return -1;
	return (ld)(a.b - b.b) / (ld)(b.a - a.a);
}
vector<line> cht;
void add(line a)
{
	while (cht.size() >= 2 && inter(cht.end()[-2], cht.end()[-1]) > inter(cht.end()[-2], a)) cht.pop_back();
	while (cht.size() >= 1 && inter(cht.end()[-1], a) < 0) cht.pop_back();
	cht.push_back(a);
}
int id = 0;
line mini(ld x)
{
	id = max(0, min((int)cht.size() - 2, id));
	while (id + 1 < cht.size() && cht[id + 1].eval(x) < cht[id].eval(x)) id++;
	return cht[id];
}
void upd(pair<ld, int>&a, pair<ld, int> b) { a = min(a, b); }
pair<ld, int> eval(vector<seg> v, ld price)
{
	cht.clear(), id = 0;
	int n = v.size();
	vector<pair<ld, int> > dp(n);
	add({ 0, (ld)sq(v.back().r + 1) });
	for (int r = 0; r < n; r++)
	{
		dp[r] = { sq(v[r].r - v[0].l + 1) + price, 1 };
		line l = mini(v[r].r);
		upd(dp[r], { l.eval(v[r].r) + sq(v[r].r) + price, l.val + 1 });
		if (r == n - 1) 
			return dp[r];
		line nw;
		nw.a = -2. * (v[r + 1].l - 1);
		nw.b = dp[r].first + sq(v[r + 1].l - 1) - sq(max(0, v[r].r - v[r + 1].l + 1));
		nw.val = dp[r].second;
		add(nw);
	}
}
long long take_photos(int n, int m, int k, vector<int> l, vector<int> r)
{
	vector<seg> v;
	for (int i = 0; i < n; i++)
	{
		if (r[i] < l[i]) swap(l[i], r[i]);
		v.push_back({ l[i], r[i] });
	}
	sort(v.begin(), v.end(), cmp);
	vector<seg> v2;
	for (seg i : v) if (v2.empty() || v2.back().r < i.r) v2.push_back(i);
	v = v2;
	n = v.size();
	k = min(k, n);
	ld lo = 0., hi = sq(m);
	for (int it = 0; it < 100; it++)
	{
		ld mi = (lo + hi) / 2.;
		if (eval(v, mi).second > k) lo = mi;
		else hi = mi;
	}
	pair<ld, int> p = eval(v, hi);
	p.first -= (ld)k * hi;
	return (ll)(p.first + 0.3);
}

Compilation message (stderr)

aliens.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens.cpp: In function 'line mini(ld)':
aliens.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  while (id + 1 < cht.size() && cht[id + 1].eval(x) < cht[id].eval(x)) id++;
      |         ~~~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'std::pair<long double, int> eval(std::vector<seg>, ld)':
aliens.cpp:68:29: warning: control reaches end of non-void function [-Wreturn-type]
   68 |  vector<pair<ld, int> > dp(n);
      |                             ^

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