Submission #557092

#	Time	Username	Problem	Language	Result	Execution time	Memory
557092		fuad27	Aliens (IOI16_aliens)	C++17	25 / 100	2062 ms	22228 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
using ll = long long;
const ll C = 2e6 + 10;
const ll N = 1e5 + 10;
const ll inf = 2e18;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	for(int i = 0;i<n;i++) {
		if(r[i] > c[i]) {
			swap(r[i], c[i]);
		}
	}
	vector<pair<long long,long long>> v;
	{
		vector<pair<long long, long long>> d;
		for(int i = 0;i<n;i++)d.push_back(make_pair(r[i], -c[i]-1));
		sort(d.begin(), d.end());
		for(int i = 0;i<n;i++)d[i].second*=-1;
		long long mxr = -inf;
		for(int i = 0; i<n; i++) {
			if(d[i].second > mxr) {
				v.push_back(make_pair(d[i].second, d[i].first));
				mxr = d[i].second;
			}
		}
	}
	sort(v.begin(), v.end());
	n = v.size();
	long long dp[k+1][n+1];
	for(int i = 0;i<=n;i++)dp[0][i] = inf;
	for(int i = 0;i<=k;i++)dp[i][0] = 0;
	for(int j = 1;j<=k;j++) {
		for(int i = 1;i<=n;i++) {
			long long mx = (v[i-1].first-v[i-1].second);
			dp[j][i] = inf;
			for(int z = i;z>=1;z--) {
				mx = (long long)v[i-1].first-v[z-1].second;
				long long val = dp[j-1][z-1]+mx*mx;
				if(z!=1 and v[z-2].first > v[z-1].second) {
					val-=(v[z-2].first-v[z-1].second)*(v[z-2].first-v[z-1].second);
				}
				dp[j][i] = min(dp[j][i], val);
			}
		}
	}
	return dp[k][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