제출 #130547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130547		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>1 && 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;
        	}
         
        	LL l,rr;
        	l=0;
        	rr=sq((LL)M);
        	k=min(k,n);
        	LL mid,ans=inf;
        	while(l<=rr){
        		mid=(l+rr)>>1;
        		x=is_ok(mid);
        		if(x==k)	return dp[n]-k*mid;
        		if(x<k){rr=mid-1;    			ans=min(ans,dp[n]-x*mid);}
        		else{
        			l=mid+1;
        		}
        	}
            return ans;
        }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:37:17: 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