Submission #341356

#	Time	Username	Problem	Language	Result	Execution time	Memory
341356		peijar	Aliens (IOI16_aliens)	C++17	25 / 100	2086 ms	22380 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
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 <= 500 and dim <= 1000)
	{
		vector<pair<int, int>> points(nbInteret);
		for (int i(0); i < nbInteret; ++i)
			points[i] = make_pair(min(vx[i], vy[i]), max(vx[i], vy[i]));
		sort(points.begin(), points.end(),
				[](pair<int, int> a, pair<int, int> b)
				{
					if (a.first == b.first)
						return a.second > b.second;
					return a.first < b.first;
				});
		vector<pair<int, int>> cur;
		for (auto p : points)
			if (cur.empty() or p.second > cur.back().second)
				cur.push_back(p);
		points = move(cur);
		vector<vector<ll>> dp(nbPhotos+1, vector<ll>(SZ(points)+1, INF));
		for (int i(0); i <= nbPhotos; ++i)
			dp[i][0] = 0;
		for (int photos(1); photos <= nbPhotos; photos++)
			for (int take(1); take <= SZ(points); ++take)
			{
				dp[photos][take] = dp[photos-1][take];
				for (int lst_photo(1); lst_photo <= take; ++lst_photo)
				{
					ll baseArea = dp[photos-1][take-lst_photo]
						+ sq(points[take-1].second - points[take-lst_photo].first+1);
					ll remArea=0;
					if (lst_photo != take and points[take-lst_photo].first <= points[take-lst_photo-1].second)
						remArea = sq(1 - points[take-lst_photo].first + points[take-lst_photo-1].second);
										
					dp[photos][take] = min(dp[photos][take], baseArea - remArea);
				}

			}
		return dp[nbPhotos][SZ(points)];
	}
}

Compilation message (stderr)

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

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