제출 #951076

#제출 시각아이디문제언어결과실행 시간메모리
951076sleepntsheepAliens (IOI16_aliens)C11
100 / 100
201 ms8372 KiB
unsigned X=12345; int rand_(){return(X*=3)>>1;} long long hi(long long a,long long b){return a>b?a:b;} int(*compar)(int,int); void sort_(int*aa,int l,int r) { while(l<r) { int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)]; while(j<k) switch(compar(aa[j],p)) { case 0:++j;break; case -1:t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;break; case 1:t=aa[--k],aa[k]=aa[j],aa[j]=t;break; } sort_(aa,l,i); l=k; } } #include "aliens_c.h" #include<string.h> long long lo(long long a,long long b){return a<b?a:b;} typedef struct { long long m, c, i; } line; #define N 100001 int n,m,k,r[N],c[N],*r0,*c0; long long ans; int comparpoint0(int i,int j) { if(r0[i]==r0[j])return c0[i]>c0[j]?-1:c0[i]<c0[j]?1:0; return r0[i]<r0[j]?-1:r0[i]>r0[j]?1:0; } void filter_covered() { int real_n=0,last_noncvered=-1; static int o[100002]={0}; for(int i=0;i<n;++i)o[i]=i; compar=comparpoint0; sort_(o,0,n); for(int i=0;i<n;++i) { int j=o[i],cver=last_noncvered>=c0[j]; if(!cver) ++real_n,r[real_n]=r0[j],c[real_n]=c0[j],last_noncvered=c0[j]; } n=real_n; } line cht[N<<1]; int head,tail; double intersectx(line a,line b) { return (b.c-a.c)*1.0L/(a.m-b.m); } void chtadd(line k) { while(head-tail>1&&intersectx(k,cht[head-1])<intersectx(cht[head-1],cht[head-2]))--head; cht[head++]=k; } line chtqry(long long x) { while(head-tail>1&&intersectx(cht[tail],cht[tail+1])<x)++tail; return cht[tail]; } #define ASSERT(x) if (!(x)) __builtin_trap() long long sq(long long x){ return x*x;} long long what(long long lambda,int*count) { head=tail=0; static long long dp[N]; static int use[N]={0}; dp[0]=0; use[0]=0; for(int i=1;i<=n;++i) { long long L=r[i]-1; long long intersect = i>1 ? sq(hi(0,c[i-1]-L)) : 0; chtadd((line){-2*L,L*L+lambda+dp[i-1] - intersect, i-1}); line best=chtqry(c[i]); dp[i]=best.m*c[i]+best.c+1ll*c[i]*c[i]; use[i]=use[best.i]+1; } *count=use[n]; return dp[n]; } long long take_photos(int n0, int m0, int k0, int* r00, int* c00) { n=n0,m=m0,k=k0; /* preprocess point - turn to 1-indexed, turn to right diagonal */ for(int i=0;i<n;++i) { ++r00[i],++c00[i]; if(r00[i]>c00[i]){int tt=r00[i];r00[i]=c00[i];c00[i]=tt;} } r0=r00,c0=c00; filter_covered(); if(k>n)k=n; int count; long long l=0,r=1e15; while(l<=r) { long long o=l+(r-l)/2; what(o,&count); if(count>k) l=o+1; else r=o-1; } ans=what(r+1,&count); return ans - k*(r+1ll); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...