제출 #69225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69225		Sa1378	Aliens (IOI16_aliens)	C++17	0 / 100	3 ms	944 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];

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){i--;n--;continue;}
		maxi=-a[i].second;
	}
	for(int i=1;i<=n;i++)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;
	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]+(a[i].second-a[j].first+1)*(a[i].second-a[j].first+1)-
						((j>1)?((a[j-1].second-a[j].first+1)*(a[j-1].second-a[j].first+1)):0));
			if(i==n)ans=min(ans,dp[(t&1)][i]);
		//	cout<<t<<" "<<i<<" "<<dp[(t&1)][i]<<"\n";
		}
	return ans;
}

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