Submission #341334

#	Time	Username	Problem	Language	Result	Execution time	Memory
341334		peijar	Aliens (IOI16_aliens)	C++17	4 / 100	2 ms	492 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

ll sq(ll x) {return x * x;}

ll take_photos(int nbInteret, int dim, int nbPhotos, vector<int> vy, vector<int> vx) 
{
	if (nbInteret <= 50 and dim <= 100 and nbPhotos == nbInteret)
	{
		vector<vector<bool>> marked(dim, vector<bool>(dim));
		for (int i(0); i < nbInteret; ++i)
		{
			int a = min(vy[i], vx[i]);
			int b = max(vy[i], vx[i]);
			for (int y(a); y <= b; ++y)
				for (int x(a); x <= b; ++x)
					marked[y][x] = true;
		}
		ll ret(0);
		for (auto v : marked)
			for (auto w : v)
				ret += w;
		return ret;
	}
	if (nbInteret <= 500 and dim <= 1000)
	{
		sort(vy.begin(), vy.end());
		vector<vector<ll>> dp(nbPhotos+1, vector<ll>(nbInteret+1));
		for (int i(0); i <= nbPhotos; ++i)
			dp[i][0] = 0;
		for (int i(1); i <= nbInteret; ++i)
			dp[0][i] = INF;
		for (int photos(1); photos <= nbPhotos; ++photos)
			for (int take(1); take <= nbInteret; ++take)
			{
				dp[photos][take] = INF;
				for (int lst_photo(0); lst_photo <= take; ++lst_photo)
					dp[photos][take] = min(dp[photos][take], sq(1+vy[take-1]-vy[take-lst_photo-1]) + (lst_photo == take ? 0 : dp[photos-1][take-lst_photo]));
			}
		return dp[nbPhotos][nbInteret];
	}
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

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