Submission #740085

#	Time	Username	Problem	Language	Result	Execution time	Memory
740085		Abrar_Al_Samit	Aliens (IOI16_aliens)	C++17	60 / 100	2060 ms	7084 KiB

aliens

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

const long long INF = 1e18;

struct line {
	long long m, c;
	line(long long _m = 0, long long _c = 0) {
		m = _m, c = _c;
	}

	long long eval(long long x) {
		return m * x + c;
	}

	long long isecX(line b) {
		return ((long double) (b.c-c)) / (m - b.m);
	}
};
struct CHT {
	deque<line>dq;
	int N = 0;

	void insert(line l) {
		while(N>=2 && l.isecX(dq[N-1]) < dq[N-1].isecX(dq[N-2])) dq.pop_back(), --N;
		dq.push_back(l);
		++N;
	}	
	long long query(int x) {
		while(N>=2 && dq[0].eval(x)>dq[1].eval(x)) dq.pop_front(), --N;
		return dq[0].eval(x);
	}
};

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;
	// }

	//optimize it with CHT
	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);
		CHT myCHT;
		myCHT.insert(line(ranges[n-1].second, sq(ranges[n-1].second)));
		for(int i=n-1; i>=0; --i) {
			long long x = -2*(ranges[i].first-1);
			long long y = myCHT.query(x);
			new_dp[i] = y + sq(ranges[i].first-1);

			if(i) {
				long long isec = max(0, ranges[i-1].second-ranges[i].first+1);
				myCHT.insert(line(ranges[i-1].second, 
				dp[i] + sq(ranges[i-1].second) - sq(isec)));
			}
		}
		dp = new_dp;
	}


	//Aliens' Trick!


	return dp[0];
}   

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