제출 #69236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69236		Sa1378	Aliens (IOI16_aliens)	C++17	25 / 100	182 ms	1136 KiB

aliens

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

ll dp[2][N];
pair <int,int> a[N];
vector <pair<int,int> > b;

ll take_photos(int n, int m, int k,vector<int> r,vector<int> c)
{
	for(int i=1;i<=n;i++)a[i]={min(r[i-1],c[i-1]),-max(r[i-1],c[i-1])};
	sort(a+1,a+n+1);
	int maxi=-1;
	for(int i=1;i<=n;i++)
	{
		if(-a[i].second<=maxi){continue;}
		maxi=-a[i].second;
		b.push_back(a[i]);
	}
	n=b.size();
	for(int i=1;i<=n;i++)a[i]=b[i-1],a[i].second*=-1;//,cout<<a[i].first<<" "<<a[i].second<<"\n";
	dp[0][0]=0;
	for(int i=1;i<N;i++)dp[0][i]=INF;
	ll ans=INF;
	a[0]={-100,-100};
	for(int t=1;t<=k;t++)
		for(int i=1;i<=n;i++)
		{
			dp[(t&1)][i]=INF;
			for(int j=i;j>0;j--)
				dp[(t&1)][i]=min(dp[(t&1)][i],dp[!(t&1)][j-1]+1LL*(a[i].second-a[j].first+1)*(a[i].second-a[j].first+1)-
						1LL*(max(0,(a[j-1].second-a[j].first+1))*max(0,(a[j-1].second-a[j].first+1))));
			if(i==n)ans=min(ans,dp[(t&1)][i]);
	//		cout<<t<<" "<<i<<" "<<dp[(t&1)][i]<<"\n";
		}
	return ans;
}

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