Submission #139009

#	Time	Username	Problem	Language	Result	Execution time	Memory
139009		nvmdava	Aliens (IOI16_aliens)	C++17	0 / 100	2 ms	424 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second

const double E = 0.000001;

struct Line{
	int id;
	double x, y, g;

	Line(int _id, int _x, int _y, int _g){
		id = _id;
		x = _x;
		y = _y;
		g = _g;
	}

	double cross(double y_, double g_){
		return (y - y_) / (g - g_);
	}

	double query(double xx){
		return y - g * xx;
	}
};

int cnt[100005];
double ans[100005];
vector<Line> line;
int n;
vector<pair<int, int> > tmp, a;
bool ooo = 0;
void calc(double c){
	line.clear();
	int it = 0, sz = 0;
	line.push_back(Line(0, 0, a[1].ff * a[1].ff, 2 * a[1].ff));
	if(ooo) cout<<a[1].ff * a[1].ff<<' '<<2 * a[1].ff<<'\n';
	for(int i = 1; i <= n; i++){
		while(it < sz && line[it + 1].x <= a[i].ss)
			it++;
		
		ans[i] = line[it].query(a[i].ss) + c + a[i].ss * a[i].ss;
		cnt[i] = cnt[line[it].id] + 1;
		if(i == n) break;
		double xx = max(0, a[i].ss - a[i + 1].ff);
		double yy = ans[i] + a[i + 1].ff * a[i + 1].ff - xx * xx;
		double gg = 2 * a[i + 1].ff;
		if(ooo)cout<<yy<<' '<<gg<<'\n';
		while(sz >= 0 && line[sz].cross(yy, gg) <= line[sz].x){
			line.pop_back();
			sz--;
		}
		sz++;
		line.push_back(Line(i,
			sz == 0 ? 0 : line[sz - 1].cross(yy, gg), 
			yy, 
			gg));
		it = min(it, sz);
	}
} 


long long take_photos(int n, int qq, int k, std::vector<int> rr, std::vector<int> c) {
	
	for(int i = 0; i < n; i++)
		tmp.push_back({min(rr[i], c[i]), -max(c[i], rr[i])});
	int mxm = -1;
	sort(tmp.begin(), tmp.end());
	a.push_back({-1, -1});
	if(ooo)cout<<'\n';
	for(auto& x : tmp){
		if(mxm < -x.ss){
			a.push_back({x.ff, 1 - x.ss});
			mxm = -x.ss;
			if(ooo)cout<<x.ff<<' '<<1 - x.ss<<'\n';
		}
	}
	if(ooo) cout<<'\n';
	
	::n = n = a.size() - 1;
	double l = 0, r = 1000000000;

	while(l + E < r){
		double m = (l + r) / 2;
		calc(m);
		if(cnt[n] <= k) r = m;
		else l = m;
	}
	calc(r);

	return floor(ans[n] - cnt[n] * r); 
}

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