Submission #165200

#	Time	Username	Problem	Language	Result	Execution time	Memory
165200		johutha	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	504 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <vector>
#include <algorithm>

#define int long long

using namespace std;

struct dpstruct
{
	int n;
	int k;
	vector<int> l;
	vector<int> r;

	int cost(int a, int b)
	{
		b--;
		int bs = r[b] - l[a] + 1;
		int ovlp = 0;
		if (a > 0) ovlp = max(r[a - 1] - l[a] + 1, 0ll);
		int ret = (bs*bs) - (ovlp*ovlp);
		// cerr << a << " " << b << " " << bs << " " << ovlp << " " << ret << "\n";
		return ret;
	}

	int calc()
	{
		k = min(k, n);
		vector<int> dp(n + 1, 1e17);
		vector<int> olddp(n + 1, 1e17);

		dp[0] = 0;
		olddp[0] = 0;

		for (int i = 0; i < k; i++)
		{
			swap(dp, olddp);

			int curr = 0;

			for (int j = 1; j <= n; j++)
			{
				while (curr < j - 1)
				{
					if (olddp[curr] + cost(curr, j) >= olddp[curr + 1] + cost(curr + 1, j)) curr++;
					else break;
				}
				dp[j] = olddp[curr] + cost(curr, j);
			}
			/*
			for (int j : dp) cerr << j << " ";
			cerr << "\n";
			*/
		}

		return dp[n];
	}
};


int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c)
{
    vector<pair<int,int>> prs;

	for (int i = 0; i < n; i++)
	{
		prs.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
	}

	sort(prs.begin(), prs.end());

	vector<int> nl;
	vector<int> nr;

	nl.push_back(prs[0].first);
	nr.push_back(-prs[0].second);

	int last = -prs[0].second;

	for (int i = 1; i < n; i++)
	{
		prs[i].second = -prs[i].second;
		if (last < prs[i].second)
		{
			nl.push_back(prs[i].first);
			nr.push_back(prs[i].second);
		}
		last = max(prs[i].second, last);
	}

	dpstruct dps;
	dps.n = nl.size();
	dps.k = k;
	dps.l = nl;
	dps.r = nr;

	return dps.calc();
}

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