제출 #96352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96352		fefe	Aliens (IOI16_aliens)	C++17	4 / 100	2 ms	424 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
#define MAX_N 100005
#define sq(x) ((x)*(x)) 
#define inf (1LL<<60)
using namespace std;
typedef long long LL;
struct node{
	LL x,y,i;
}V[MAX_N],line[MAX_N];
LL n,m,k,s,e;
LL dp[MAX_N],from[MAX_N];
bool is_delect(node x,node y,node z){return (x.x-z.x)*(y.y-x.y)>=(x.x-y.x)*(z.y-x.y)?true:false;}
void add(LL x,LL y,LL i){
	while(e-s>2 && is_delect(line[e-2],line[e-1],{x,y}))	e--;
	line[e++]={x,y,i};
}
LL get_val(LL i,LL x){return line[i].x*x+line[i].y;}
LL is_ok(LL x){
	LL i;
	s=e=0;
	add(-2*V[1].x,sq(V[1].x)-2*V[1].x,0);
	for(i=1;i<=n;i++){
		while(e-s>1 && get_val(s,V[i].y)>=get_val(s+1,V[i].y))	s++;
		dp[i]=get_val(s,V[i].y)+sq(V[i].y+1)+x;
		from[i]=line[s].i;
		add(-2*V[i+1].x,sq(V[i+1].x)+dp[i]-2*V[i+1].x-sq(max(0LL,V[i].y-V[i+1].x+1)),i);
	}
	i=n;
	LL c;
	for(c=0;i;i=from[i],c++);

	return c;
}

long long take_photos(int N, int M, int K, std::vector<int> r, std::vector<int> c) {
	LL i,x,y;
	n=N;
	m=M;
	k=K;
	for(i=1;i<=n;i++)	V[i]={min(r[i-1],c[i-1]),max(r[i-1],c[i-1])};
	sort(V+1,V+n+1,[&](const node x,const node y){return (x.x==y.x)?x.y>y.y:x.x<y.x;});
	m=n;n=0;
	x=-inf;
	for(i=1;i<=m;i++){
		if(x>=V[i].y)	continue;
		V[++n]=V[i];
		x=V[i].y;
	}

	is_ok(0);
	return dp[n];
	LL l,rr;
	l=0;
	rr=sq((LL)M);
	k=min(k,n);
	while(l<=rr){
		LL mid=(l+rr)>>1;
		x=is_ok(mid);
		if(x==k)	return dp[n]-k*mid;
		if(x<k)	rr=mid-1;
		else	l=mid+1;
	}
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:37:9: warning: unused variable 'y' [-Wunused-variable]
  LL i,x,y;
         ^

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