Submission #828534

#	Time	Username	Problem	Language	Result	Execution time	Memory
828534		caganyanmaz	Aliens (IOI16_aliens)	C++14	12 / 100	82 ms	2332 KiB

aliens

#include <bits/stdc++.h>

#define pb push_back
#define int int64_t
using namespace std;

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 505;
constexpr static int INF = 1e17;
int dp[MXN][MXN];
long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c)
{
	vector<array<int, 2>> v;
	for (int i = 0; i < n; i++)
	{
		if (c[i] > r[i])
			swap(r[i], c[i]);
		v.pb({c[i], r[i]});
	}
	sort(v.begin(), v.end());
	debug(n, v);
	int last = 0;
	set<int> s;
	s.insert(0);
	for (int i = 1; i < n; i++)
	{
		debug(last, v[last]);
		if (v[last][1] >= v[i][1])
			continue;
		s.insert(i);
		if (v[last][0] == v[i][0] && v[i][1] >= v[last][1])
		{
			debug(last, i, v[last][0], v[i][0]);
			s.erase(last);
		}
		last = i;
	}
	debug(s);
	vector<array<int, 2>> pos;
	for (int nv : s)
		pos.pb(v[nv]);
	debug(pos);
	for (int i = 0; i <= pos.size(); i++)
		for (int j = 0; j <= k; j++)
			dp[i][j] = INF;
	dp[0][0] = 0;
	for (int i = 1; i <= pos.size(); i++)
	{
		for (int j = 1; j <= k; j++)
		{
			for (int l = 0; l < i; l++)
			{
				dp[i][j] = min(dp[i][j], dp[l][j-1] + (1 + pos[i-1][1] - pos[l][0]) * (1 + pos[i-1][1] - pos[l][0]));
				debug(l, i, j, dp[i][j]);
			}
		}
	}
	int best = INF;

	for (int i = 0; i <= k; i++)
	{
		debug(pos.size(), i, dp[pos.size()][i]);
		best = min(best, dp[pos.size()][i]);
	}
	return best;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0; i <= pos.size(); i++)
      |                  ~~^~~~~~~~~~~~~
aliens.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 1; i <= pos.size(); i++)
      |                  ~~^~~~~~~~~~~~~

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