Submission #116418

#	Time	Username	Problem	Language	Result	Execution time	Memory
116418		davitmarg	Aliens (IOI16_aliens)	C++17	60 / 100	2072 ms	358888 KiB

aliens

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

struct line
{
	LL k, b;
	line(LL K = 0, LL B = 0)
	{
		k = K;
		b = B;
	}
};

vector<line> convex;

bool del(line a,line b,line c)
{
	pair<LL, LL> x1, x2;
	x1 = MP(c.b - a.b, a.k - c.k);
	x2 = MP(c.b - b.b, b.k - c.k);
	//assert(x1.second && x2.second);
	if (b.k == c.k)
		return c.b >= b.b;
	if ((x1.second < 0) == (x2.second < 0))
		return x1.first * x2.second > x2.first * x1.second;
	else
		return x1.first * x2.second < x2.first * x1.second;
}

LL getY(LL x,line p)
{
	return x * p.k + p.b;
}

void build()
{
	convex.clear();
}

void add(line p)
{
	while (convex.size() >= 2 && del(convex[convex.size() - 2], convex[convex.size() - 1], p) )
		convex.pop_back();
	convex.PB(p);
}

bool check(int pos,LL x)
{
	if (pos + 1 != convex.size() && getY(x, convex[pos + 1]) < getY(x, convex[pos]))
		return 0;
	if (pos - 1 >= 0 && getY(x, convex[pos]) < getY(x, convex[pos - 1]))
		return 0;
	return 1;
}

LL get(LL x)
{
	int l, r, m;
	LL ans = -mod * mod;
	l = 0;
	r = convex.size() - 1;
	while (l <= r)
	{
		m = (l + r) / 2;
		ans = max(ans, getY(x, convex[m]));

		if (check(m, x))
			l = m + 1;
		else
			r = m - 1;
	}
	return ans;
}

int n, m, k;
vector<pair<int, int>> c;
vector<pair<LL, LL>> a,p;
vector<vector<LL>> dp;
int Main()
{
	for (int i = 0; i < c.size(); i++)
	{
		if (c[i].first > c[i].second)
			swap(c[i].first, c[i].second);
		p.PB(MP(c[i].first, c[i].second));
	}

	sort(all(p), [](pair<LL, LL> a, pair<LL, LL> b) {
		if (a.first != b.first)
			return a.first < b.first;
		return b.first > a.first;
	});

	a.PB(MP(-1, -1));
	for (int i = 0; i < p.size(); i++)
		if (a.back().second < p[i].second)
			a.PB(p[i]);
	n = a.size() - 1;
	k = min(k, n);

	dp.resize(k + 5, vector<LL>(n + 5, 0));
	
	for (int i = 1; i <= n; i++)
		dp[1][i] = (a[i].second - a[1].first + 1) * (a[i].second - a[1].first + 1);

	for (int i = 2; i <= k; i++)
	{
		build();
		for (int j = i - 1; j <= i - 1; j++)
			add(line(2 * (a[j + 1].first - 1), max(a[j].second - a[j + 1].first + 1, 0ll) * max(a[j].second - a[j + 1].first + 1, 0ll) - dp[i - 1][j] - (a[j + 1].first - 1) * (a[j + 1].first - 1)));
		for (int j = i; j <= n; j++)
		{
			dp[i][j] = -get(a[j].second) + a[j].second* a[j].second;
			if (j != n)
				add(line(2 * (a[j + 1].first - 1), max(a[j].second - a[j + 1].first + 1, 0ll) * max(a[j].second - a[j + 1].first + 1, 0ll) - dp[i - 1][j] - (a[j + 1].first - 1) * (a[j + 1].first - 1)));
		}
	}
	return 0;
}

LL take_photos(int N, int M, int K, vector<int> y, vector<int> x)
{
	n = N;
	m = M;
	k = K;
	while (!y.empty())
	{
		c.PB(MP(y.back(),x.back()));
		y.pop_back();
		x.pop_back();
	}
	Main();
	return dp[k][n];
}


#ifdef death

int main()
{
	int N, M, K;
	vector<int> R, C;
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
		R.PB(0);
		C.PB(0);
		cin >> R.back() >> C.back();
	}
	cout << take_photos(N, M, K, R, C) << endl;

	return 0;
}

#endif

/*


3 4 3
0 1
1 2
2 3

5 6 4
0 1
1 2
2 3
3 4
4 5

2 6 2
1 4
4 1

5 7 2
0 3
4 4
4 6
4 5
4 6

*/

Compilation message (stderr)

aliens.cpp: In function 'bool check(int, long long int)':
aliens.cpp:72:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (pos + 1 != convex.size() && getY(x, convex[pos + 1]) < getY(x, convex[pos]))
      ~~~~~~~~^~~~~~~~~~~~~~~~
aliens.cpp: In function 'int Main()':
aliens.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < c.size(); i++)
                  ~~^~~~~~~~~~
aliens.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++)
                  ~~^~~~~~~~~~

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