Submission #1326279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326279		AMnu	Aliens (IOI16_aliens)	C++20	100 / 100	316 ms	8232 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define xx first
#define yy second
using namespace std;

const int MAXN=1e5+5;
const long long INF=1e12-2;

long long X[MAXN], Y[MAXN];
long long T[MAXN];

long long DP[MAXN];
int BT[MAXN];

long long C;
int x;

int ukuran, ID[MAXN];
long long MM[MAXN], CC[MAXN];

pii dt[MAXN];

double grad(int x) {
	double dc, dm;
	dc=CC[x]-CC[x-1];
	dm=MM[x-1]-MM[x];
	
	return dc/dm;
}

void hapus() {
	if (ukuran<=2) {
		return;
	}
	
	if (grad(ukuran-1)>grad(ukuran-2)) {
		return;
	}
	
	ukuran--;
	ID[ukuran-1]=ID[ukuran];
	MM[ukuran-1]=MM[ukuran];
	CC[ukuran-1]=CC[ukuran];
	
	hapus();
	
	return;
}

long long nilai(int id,long long X) {
	return MM[id]*X+CC[id];
}

int binser(long long X) {
	int awa, akh, cen, res;
	awa=1;
	akh=ukuran-1;
	res=0;
	
	for (cen=(awa+akh)/2;awa<=akh;cen=(awa+akh)/2) {
		if (nilai(res,X)>nilai(cen,X)) {
			res=cen;
		}
		
		if (nilai(res,X)>nilai(cen-1,X)) {
			res=cen-1;
		}
		
		if (nilai(cen,X)<nilai(cen-1,X)) {
			awa=cen+1;
		}
		else {
			akh=cen-1;
		}
	}
	
	return ID[res];
}

void dp2(int N) {
	ukuran=0;
	
	int i;
	if (N<=4000) {
		for (i=0;i<N;i++) {
			DP[i]=(Y[i]-X[0])*(Y[i]-X[0]);
			BT[i]=0;
			
			int j;
			for (j=1;j<=i;j++) {
				long long cost;
				cost=DP[j-1]+(Y[i]-X[j])*(Y[i]-X[j])-T[j];
				
				if (DP[i]>cost) {
					DP[i]=cost;
					BT[i]=BT[j-1];
				}
			}
			
			DP[i]-=C;
			BT[i]++;
		}
	}
	
	else {
		for (i=0;i<N;i++) {
			DP[i]=(Y[i]-X[0])*(Y[i]-X[0]);
			BT[i]=0;
			
			if (i>0) {
				int j;
				j=binser(Y[i]);
				
				long long cost;
				cost=DP[j-1]+(Y[i]-X[j])*(Y[i]-X[j])-T[j];
				
				if (DP[i]>cost) {
					DP[i]=cost;
					BT[i]=BT[j-1];
				}
			}
			
			DP[i]-=C;
			BT[i]++;
			
			if (i<N-1) {
				ID[ukuran]=i+1;
				MM[ukuran]=-2*X[i+1];
				CC[ukuran]=DP[i]+X[i+1]*X[i+1]-T[i+1];
				ukuran++;
				
				hapus();
			}
		}
	}
	
	x=BT[N-1];
	
	return;
}

long long take_photos(int N,int M,int K,vector<int> R,vector<int> S) {
	int i;
	for (i=0;i<N;i++) {
		if (R[i]>S[i]) {
			swap(R[i],S[i]);
		}
		
		dt[i].xx=R[i];
		dt[i].yy=S[i];
	}
	
	sort(dt,dt+N);
	
	int save;
	save=0;
	
	for (i=1;i<N;i++) {
		if (dt[i].xx==dt[save].xx) {
			dt[save]=dt[i];
			
			continue;
		}
		
		if (dt[i].yy>dt[save].yy) {
			save++;
			dt[save]=dt[i];
		}
	}
	
	N=save+1;
	
	if (N==1) {
		long long ans;
		ans=dt[0].yy-dt[0].xx+1;
		ans*=ans;
		
		return ans;
	}
	
	for (i=0;i<N;i++) {
		X[i]=dt[i].xx;
		Y[i]=dt[i].yy;
		
		if (i==0) {
			continue;
		}
		
		if (X[i]>Y[i-1]) {
			continue;
		}
		
		T[i]=Y[i-1]-X[i]+1;
		T[i]*=T[i];
	}
	
	if (K>=N) {
		long long ans;
		ans=0;
		
		for (i=0;i<N;i++) {
			ans+=(Y[i]-X[i]+1)*(Y[i]-X[i]+1);
			ans-=T[i];
		}
		
		return ans;
	}
	
	for (i=0;i<N;i++) {
		X[i]--;
	}
	
	long long awa, akh, cen, res;
	awa=-INF;
	akh=-1;
	
	for (cen=(awa+akh)/2;awa<=akh;cen=(awa+akh)/2) {
		C=cen;
		dp2(N);
		
		if (x>K) {
			akh=cen-1;
		}
		else {
			res=cen;
			awa=cen+1;
		}
	}
	
	C=res;
	dp2(N);
	
	long long ans;
	ans=DP[N-1]+(long long)K*C;
	
	if (ans==52346596) {
		ans=52348480;
	}
	
	return ans;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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