Submission #69667

#	Time	Username	Problem	Language	Result	Execution time	Memory
69667		Sa1378	Aliens (IOI16_aliens)	C++17	60 / 100	251 ms	29240 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define N ((int)50*1001)
#define INF ((ll)1e18)

pair <int,int> a[N],ex[N];
ll dp[2][N];
deque <pair<ll,ll> > lines;

ld barkhord_x(pair <ll,ll> x,pair<ll,ll> y)
{
	return (ld)(x.second-y.second)/(y.first-x.first);
}

ll take_photos(int n, int m, int k,vector<int> r,vector<int> c)
{
	for(int i=1;i<=n;i++)ex[i]={min(r[i-1],c[i-1])-1,-max(c[i-1],r[i-1])};
	sort(ex+1,ex+n+1);
	int maxi=-1,n2=0;
	for(int i=1;i<=n;i++)
		if(-ex[i].second>maxi)
			a[++n2]={ex[i].first,-ex[i].second},maxi=-ex[i].second;
	n=n2;
	dp[0][0]=0;
	for(int i=1;i<=n;i++)dp[0][i]=INF;
	a[0]={-10,-10};
	ll ans=INF;
	for(int t=1;t<=k;t++)
	{
		bool p=(t&1);
		lines.clear();
		dp[p][0]=INF;
		for(int i=1;i<=n;i++)
		{
			pair <ll,ll> tmp;tmp={-2LL*a[i].first,
			dp[!p][i-1]+1LL*a[i].first*a[i].first-1LL*max(0,a[i-1].second-a[i].first)*max(0,a[i-1].second-a[i].first)};
			while(lines.size()>1 && barkhord_x(lines.back(),tmp)<=barkhord_x(lines[(int)lines.size()-2],lines.back()))
				lines.pop_back();
			lines.push_back(tmp);
			while(lines.size()>1 && barkhord_x(lines[0],lines[1])<=a[i].second)lines.pop_front();
			dp[p][i]=1LL*a[i].second*a[i].second+1LL*a[i].second*lines[0].first+lines[0].second;
		}
		ans=min(ans,dp[p][n]);
	}
	return ans;
}

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