Submission #740071

#	Time	Username	Problem	Language	Result	Execution time	Memory
740071		Abrar_Al_Samit	Aliens (IOI16_aliens)	C++17	25 / 100	2071 ms	468 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;

const long long INF = 1e18;

long long sq(long long x) {
	return x * x;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	//fix the input
	vector<pair<int,int>>ranges(n);
	for(int i=0; i<n; ++i) {
		ranges[i] = {min(r[i], c[i]), max(r[i], c[i])};
	}
	sort(ranges.begin(), ranges.end(), [&] (auto x, auto y) {
		if(x.first==y.first) return x.second > y.second;
		return x.first < y.first;
	});

	vector<pair<int,int>>new_ranges;
	for(int i=0; i<n; ++i) {
		if(!new_ranges.empty() && new_ranges.back().first<=ranges[i].first
		 && new_ranges.back().second>=ranges[i].second);
		else new_ranges.push_back(ranges[i]);
	}
	ranges = new_ranges;
	n = ranges.size();

	//do naive O(n*n*k) dp
	vector<long long>dp(n+10, INF);
	for(int j=k-1; j>=0; --j) {
		dp[n] = 0;
		vector<long long>new_dp(n+10, INF);
		for(int i=n-1; i>=0; --i) {
			for(int t=i+1; t<=n; ++t) {
				long long isec = (t<n) ? max(0, ranges[t-1].second-ranges[t].first+1) : 0;
				new_dp[i] = min(new_dp[i], 
					dp[t] + sq(ranges[t-1].second - ranges[i].first + 1) - sq(isec));
			}
		}
		dp = new_dp;
	}
	return dp[0];

	//optimize it with CHT

	//Aliens' Trick!
}   

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