제출 #241321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241321		sebamarin	Aliens (IOI16_aliens)	C++14	0 / 100	2073 ms	1528 KiB

aliens

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

typedef long long ll;
typedef pair<int,int> ii;
#define db(x) cout<<#x<<" = "<<x<<"\n";
#define fore(i,a,b) for(int i=a,ggdem=b;i<ggdem;i++)
#define FIN ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(),a.end()
#define mset(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define fst first
#define snd second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


const int N=1e6+5,INF=N;
int n,m,k,r[N],c[N],dp[512][512];
ii a[N];
ll sq(ll x){return x*x;}
ll solve(int i,int j) {
	if(i==n)return 0;
	if(j==k)return INF;
	if(dp[i][j]!=-1)return dp[i][j];
	ll res=N;
	fore(st,0,m)fore(en,st,m) {
		int to=i;
		while((to<n) && st<=c[to] && c[to]<=en && st<=r[to] && r[to]<=en)to++;
		res=min(res,sq(en-st+1)+solve(to,j+1));
	}
	return dp[i][j]=res;
}
void doit(int _n,int _m,int _k,vector<int>_r,vector<int>_c) {
	n=_n;
	m=_m;
	k=_k;
	fore(i,0,n)a[i].fst=_r[i],a[i].snd=_c[i];
	sort(a,a+n);
	fore(i,0,n)r[i]=a[i].fst,c[i]=a[i].snd;
}
ll take_photos(int n,int m,int k,vector<int>r,vector<int> c) {
	memset(dp,-1,sizeof(dp));
	doit(n,m,k,r,c);
	return solve(0,0);
}
/*
int main() {FIN;
	// freopen("out","w",stdout);
	cin>>n>>m>>k;
	vector<int>r(n),c(n);
	fore(i,0,n)cin>>r[i]>>c[i];
	cout<<take_photos(n,m,k,r,c)<<"\n";
}
*/
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
---> 25
2 5 2
1 4
4 1
---> 16
*/

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