Submission #130545

#	Time	Username	Problem	Language	Result	Execution time	Memory
130545		fefe	Aliens (IOI16_aliens)	C++17	4 / 100	2 ms	380 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=0;
    	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=max(ans,dp[n]-x*mid);}
    		else{
    			l=mid+1;
    		}
    	}
        return ans;
    }

Compilation message (stderr)

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