Submission #935228

#	Time	Username	Problem	Language	Result	Execution time	Memory
935228		Cyber_Wolf	Aliens (IOI16_aliens)	C++17	100 / 100	214 ms	15920 KiB

aliens

// Problem: P6 - Aliens
// Contest: DMOJ - IOI '16
// URL: https://dmoj.ca/problem/ioi16p6
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

using namespace std;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 1e5+5;
lg n, k;
lg dp[N];
lg opt[N];
vector<array<lg, 2>> p;
vector<lg> o;

void solve(lg lambda)
{
	for(int i = 0; i <= n; i++)	dp[i] = 2e18, opt[i] = 2e18;
	dp[0] = opt[0] = 0;
	deque<lg> slope, inter;
	deque<lg> opts;
	lg sz = 1;
	opts.push_back(0);
	slope.push_back(-2*p[0][1]);
	inter.push_back(p[0][1]*p[0][1]-o[0]+dp[0]);
	for(int i = 1; i <= n; i++)
	{
		while(sz > 1 && p[i-1][0]*slope[1]+inter[1] < p[i-1][0]*slope[0]+inter[0])
		{
			opts.pop_front();
			slope.pop_front();
			inter.pop_front();
			sz--;
		}
		dp[i] = p[i-1][0]*slope.front()+inter.front()+p[i-1][0]*p[i-1][0]+lambda;
		opt[i] = opts.front()+1;
		if(i < n)
		{
			lg x = -2*p[i][1], y = p[i][1]*p[i][1]-o[i]+dp[i];
			while(sz > 1 && (inter[sz-2]-y)*(slope[sz-1]-slope[sz-2]) <= (inter[sz-2]-inter[sz-1])*(x-slope[sz-2]))
			{
				slope.pop_back();
				inter.pop_back();
				opts.pop_back();
				sz--;
			}
			slope.push_back(x);
			inter.push_back(y);
			opts.push_back(opt[i]);
			sz++;
		}
	}
	return;
}

lg take_photos(int NM, int m, int K, vector<int> r, vector<int> c)
{
	n = NM, k = K;
	set<array<lg, 2>> pt;
	for(int i = 0; i < n; i++)
	{
		if(r[i] < c[i])	swap(r[i], c[i]);
		pt.insert({r[i], -c[i]});
	}
	for(auto [x, y] : pt)
	{
		while(p.size() && p.back()[1] >= -y)	p.pop_back();
		p.push_back({x, -y});
	}
	for(auto &it : p)	it[1]--;
	lg la = -1e18;
	for(auto it : p)
	{
		if(la-it[1] > 0)	o.push_back((la-it[1])*(la-it[1]));
		else	o.push_back(0);
		la = it[0];
	}
	n = p.size();
	lg s = 0, e = 1e18, ans = m*m;
	k = min(k, n);
	while(s <= e)
	{
		lg mid = (s+e)/2;
		solve(mid);
		if(opt[n] <= k)
		{
			e = mid-1;
			ans = dp[n]-k*mid;
		}
		else{
			s = mid+1;
		}
	}
	return ans;
}

/*
m1x+c1 <= m2x+c2
m1x-m2x <= c2-c1
x <= (c2-c1)/(m1-m2)


5 7 2
0 3
4 4
4 6
4 5
4 6
*/

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