Submission #130934

#TimeUsernameProblemLanguageResultExecution timeMemory
130934fefeAliens (IOI16_aliens)C++17
4 / 100
2 ms380 KiB
#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; typedef pair<LL,LL> pil; struct node{ LL s,e; }V[MAX_N]; struct line{ LL a,b,c; }L[MAX_N]; LL n,k,ans; LL dp[MAX_N],from[MAX_N]; bool is_ok(line a,line b,line c){ return (b.b-a.b)*(b.a-c.a)<(a.a-b.a)*(c.b-b.b); } LL CHT(LL c){ LL s,e; LL i; s=e=0; L[e++]={-2*V[1].s,sq(V[1].s)-2*V[1].s,0}; for(i=1;i<=n;i++){ while(e-s>1 && L[s].a*V[i].e+L[s].b>=L[s+1].a*V[i].e+L[s+1].b) s++; dp[i]=L[s].a*V[i].e+L[s].b+sq(V[i].e+1)+c; from[i]=L[s].c; line p={-2*V[i+1].s,sq(V[i+1].s)-2*V[i+1].s+dp[i]}; if(V[i].e-V[i+1].s+1>0) p.b-=sq(V[i].e-V[i+1].s+1); p.c=i; while(e-s>1 && !is_ok(L[e-2],L[e-1],p)) e--; L[e++]=p; } for(c=0,i=n;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,s=0,e=(long long)m*m; n=N; k=K; for(i=1;i<=n;i++){ V[i].s=min(r[i-1],c[i-1]); V[i].e=max(r[i-1],c[i-1]); } sort(V+1,V+n+1,[&](const node x,const node y){return (x.s==y.s)?(x.e>y.e):(x.s<y.s);}); m=0; LL x=-10000; for(i=1;i<=n;i++){ if(x<V[i].e) V[++m]=V[i]; x=max(x,V[i].e); } n=m; sort(V+1,V+n+1,[&](const node x,const node y){return x.e<y.e;}); ans=inf; k=min(n,k); bool Z=false; LL lx=inf,lv,rx=-inf,rv; while(s<=e){ LL mid=(s+e)>>1; x=CHT(mid); if(x==k){ return dp[n]-mid*x; }else if(x<k){ rx=mid;rv=dp[n]-mid*x; e=mid-1; }else{ lx=mid;lv=dp[n]-mid*x; s=mid+1; } } return rv; }

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:59:7: warning: unused variable 'Z' [-Wunused-variable]
  bool Z=false;
       ^
aliens.cpp:60:5: warning: variable 'lx' set but not used [-Wunused-but-set-variable]
  LL lx=inf,lv,rx=-inf,rv;
     ^~
aliens.cpp:60:12: warning: variable 'lv' set but not used [-Wunused-but-set-variable]
  LL lx=inf,lv,rx=-inf,rv;
            ^~
aliens.cpp:60:15: warning: variable 'rx' set but not used [-Wunused-but-set-variable]
  LL lx=inf,lv,rx=-inf,rv;
               ^~
aliens.cpp:60:23: warning: 'rv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  LL lx=inf,lv,rx=-inf,rv;
                       ^~
#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...