Submission #69199

#	Time	Username	Problem	Language	Result	Execution time	Memory
69199		Navick	Aliens (IOI16_aliens)	C++17	25 / 100	186 ms	1104 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;

const int maxN = 510, maxK = 510;
const ll oo = 2e18;

ll las[maxN], dp[maxN], f[maxN];
int l[maxN], r[maxN];

vector <pii> que;

bool cmp(pii a1, pii a2)
{
	if(a1.F != a2.F) return a1.F < a2.F;
	return a1.S > a2.S;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    
	if(n > maxN) return -1;

	for (int i=0; i<n; i++)
	{
		if(r[i] <= c[i])
			c[i] ++;
		else r[i] ++;
		que.pb({min(r[i], c[i]), max(r[i], c[i])});
	}

	sort(que.begin(), que.end(), cmp);

	int mx = -1, cnt = 0;

	for (int i=0; i<n; i++)
	{
		if(mx >= que[i].S) continue ;
		else 
		{
			l[cnt] = que[i].F, r[cnt] = que[i].S;
			mx = max(mx, que[i].S);
			cnt ++;
		}
	}

	n = cnt;

	
	for (int i=0; i<=n; i++) las[i] = oo;
	las[0] = 0;

	for (int i=0; i<n-1; i++)
		if(r[i] > l[i + 1]) f[i] = 1LL * (r[i] - l[i + 1]) * (r[i] - l[i + 1]);
	
	for (int j=1; j<=k; j++)
	{
		dp[0] = 0;
		for (int i=1; i<=n; i++)
		{
			dp[i] = oo;
			for (int j=0; j<i; j++)
			{
				ll c;
				if(j) c = f[j - 1];
				else c = 0;

				dp[i] = min(dp[i], (ll)(r[i - 1] - l[j]) * (r[i - 1] - l[j]) - c + las[j]);
			}
		}

		for (int i=1; i<=n; i++)
			las[i] = dp[i];

	}

	return dp[n];
}

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