Submission #292677

#	Time	Username	Problem	Language	Result	Execution time	Memory
292677		VodkaInTheJar	Aliens (IOI16_aliens)	C++14	100 / 100	358 ms	14760 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
 
using namespace std;
 
const int maxn = 100003; 
const double inf = 1/.0;

struct line
{
	long long k, m, delta;  
    double p; 
    bool operator < (const long long &t) {return p < t;}
};
 
double intersection_point(line a, line b)
{
	if (a.k == b.k)
	return (a.m >= b.m ? -inf: inf);
	
	else
	return (double)(b.m - a.m) / (double)(a.k - b.k);
}
 
struct line_container
{
	vector <line> lines;
	void insert_line(long long a, long long b, long long delta)
	{
		line curr = {a, b, delta, 0};
		while (!lines.empty() && intersection_point(curr, lines.back()) <= lines.back().p)
		lines.pop_back();
		
		if (!lines.empty())
		curr.p = intersection_point(curr, lines.back());
		
		else 
		curr.p = -inf;
		
		lines.push_back(curr);
	}
	
	pair <long long, long long> query(long long pos)
	{
		auto it = lower_bound(lines.begin(), lines.end(), pos);
		it--;
		
		return {it->delta, it->k * pos + it->m};
	}
};
 
vector <pair <long long, long long> > v; 
line_container convex_hull;
long long dp[maxn];
long long delta[maxn];
 
void calc(long long x)
{
	convex_hull.lines.clear();
	dp[0] = 0; 
	delta[0] = 0; 
	convex_hull.insert_line(2 * v[0].first, -dp[0] - 1ll * v[0].first * v[0].first, 0);
	
	for (int i = 1; i <= (int)v.size(); i++)
	{
		auto curr = convex_hull.query(v[i-1].second + 1);
		
		dp[i] = -curr.second + (v[i-1].second + 1) * (v[i-1].second + 1) + x;
		delta[i] = curr.first + 1; 
		 
		if (i != (int)v.size())
		{
			long long curr_c = -dp[i] - v[i].first * v[i].first;
		    if (v[i-1].second >= v[i].first)
		    curr_c += (v[i-1].second - v[i].first + 1) * (v[i-1].second - v[i].first + 1); 
		    
			convex_hull.insert_line(2 * v[i].first, curr_c, delta[i]);
		}
	}
}
 
long long take_photos(int n, int m, int k, vector <int> r, vector <int> c)
{
	map <int, int> mp;
	for (int i = 0; i < n; i++)
	{
		r[i]++;
		c[i]++; 
		
		int ll = min(r[i], c[i]);
		int rr = max(r[i], c[i]);
 
		if (!mp.count(rr) || ll < mp[rr])
		mp[rr] = ll; 
	}
	
	for (auto i: mp)
	{ 
		while (!v.empty() && v.back().first >= i.second)
		v.pop_back();
		
		v.push_back({i.second, i.first});
	}
	
	long long low = -1e12, high = 1e12;
	while (high - low > 1)
	{ 
		long long mid = (low + high) / 2; 
		calc(mid);
		
		if (delta[(int)v.size()] >= k)
		low = mid; 
		
		else 
		high = mid; 
	}
	
	low++;
	calc(low);
	return dp[(int)v.size()] - max(1ll * delta[(int)v.size()] * low, 1ll * k * low);
}
 
 
/*
int n, k, m; 
vector <int> r, c;
int main()
{
	cin >> n >> k >> m;
	r.resize(n), c.resize(n);
	for (int i = 0; i < n; i++)
	cin >> r[i] >> c[i];
	
	cout << take_photos(n, m, k, r, c) << endl; 
}
*/

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