Submission #786583

#	Time	Username	Problem	Language	Result	Execution time	Memory
786583		AlphaBruh	Aliens (IOI16_aliens)	C++14	25 / 100	2020 ms	5076 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int>ys;
vector<int>xs;
struct p{
	int x=-1,y=-1;
};
long long min(long long a, long long b){
	if(a>b) return b;
	return a;
}
long long max(long long a, long long b){
	if(a<b) return b;
	return a;
}
vector<p> flt(){
	vector<int>ymx(m,-1);
	for(int id = 0; id < n; id++){
		if(ys[id]>xs[id]) swap(ys[id],xs[id]);
		ymx[ys[id]]=max(xs[id],ymx[ys[id]]);
	}
	p sv[100005];
	p tmp;
	int bmx=-1,cnt=0;
	for(int i = 0; i < m; i++){
		if(ymx[i]<=bmx) continue;
		tmp.y=i;
		tmp.x=ymx[i];
		bmx=ymx[i];
		sv[cnt]=tmp;
		cnt++;
	}
	vector<p>rt(cnt+1);
	tmp.x = -m;
	tmp.y = -m;
	rt[0]=tmp;
	for(int i = 1; i <= cnt; i++){
		rt[i]=sv[i-1];
	}
	n=cnt;
	k = min(n,k);
	return rt;
}
long long sq(long long x){
	return x*x;
}
long long st3(){
	vector<p>main_p(flt());
	vector<long long>dp[2];//dp[cap][first i points done]
	dp[1].assign(n+1,0);
	for(int i = 1; i <= n; i++){
		dp[1][i]=sq(main_p[i].x-main_p[1].y+1);
	}
	for(int nwk=2;nwk<=k;nwk++){
		dp[0].assign(dp[1].begin(),dp[1].end());
		for(int dne=1; dne <= n; dne++){
			for(int hbd=0; hbd<=dne;hbd++){
				dp[1][dne]=min(dp[1][dne],dp[0][hbd]+sq(main_p[dne].x-main_p[hbd+1].y+1)-sq(max(0,main_p[hbd].x-main_p[hbd+1].y+1)));
			}
		}
	}
	return dp[1][n];
}
long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C) {
    n=N;
	m=M;
	k=K;
	ys.assign(R.begin(),R.end());
	xs.assign(C.begin(),C.end());
	return st3();
}

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