Submission #935226

#	Time	Username	Problem	Language	Result	Execution time	Memory
935226		Cyber_Wolf	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 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>

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] = opt[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, int r[], 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 = -1, e = 1e15;
	k = min(k, n);
	while(e-s > 1)
	{
		lg mid = (s+e)/2;
		solve(mid);
		// cout << mid << '\n';
		// cout << dp[n]  << ' ' << opt[n] << '\n';
		if(opt[n] >= k)
		{
			s = mid;
		}
		else{
			e = mid;
		}
	}
	solve(s);
	return dp[n]-k*s;
}

int main()
{
	int n, m, k;
	cin >> n >> m >> k;
	int r[n], c[n];
	for(int i = 0; i < n; i++)
	{
		cin >> r[i] >> c[i];
	}
	cout << take_photos(n, m, k, r, c) << '\n';
	return 0;
}
/*
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
*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccqGlXWS.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccyzjnR.o:aliens.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccqGlXWS.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status