제출 #986394

#제출 시각아이디문제언어결과실행 시간메모리
986394PyqeAliens (IOI16_aliens)C++17
100 / 100
154 ms8756 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; #define mp make_pair #define fr first #define sc second const long long ub=1e12; long long nn=0,sl[100069],wg[100069],sk[100069]; pair<long long,long long> a[100069],dp[100069]; long long f(long long x,long long w) { return sl[x]*w+wg[x]; } bool cmp(long long x,long long y,long long x2,long long y2) { return mp(x/y,x%y*y2)>mp(x2/y2,x2%y2*y); } bool chk(long long x,long long y,long long y2) { return cmp(wg[x]-wg[y2],sl[y2]-sl[x],wg[x]-wg[y],sl[y]-sl[x]); } long long take_photos(int n,int m,int d,vector<int> ya,vector<int> xa) { long long i,k,x,y,y2,sz,p,sm,c,lh,rh,md,zz,zm; for(i=1;i<=n;i++) { y=ya[i-1]+1; x=xa[i-1]+1; if(x<y) { swap(x,y); } y--; a[i]={x,-y}; } sort(a+1,a+n+1); sz=n; n=0; for(i=1;i<=sz;i++) { x=a[i].fr; y=-a[i].sc; for(;n&&a[n].sc>=y;n--); n++; a[n]={x,y}; } a[n+1].sc=m+1; for(lh=0,rh=ub;lh<=rh;) { md=(lh+rh)/2; nn=0; p=0; for(i=0;i<=n;i++) { x=a[i].fr; y=a[i].sc; y2=a[i+1].sc; if(i) { for(;p<nn&&(!p||f(sk[p+1],x)<f(sk[p],x));p++); dp[i]={f(sk[p],x)+x*x+md,dp[sk[p]].sc+1}; } sl[i]=-y2*2; k=max(x-y2,0ll); wg[i]=dp[i].fr-k*k+y2*y2; for(;nn>=2&&chk(i,sk[nn],sk[nn-1]);nn--); p=min(p,nn); nn++; sk[nn]=i; } sm=dp[n].fr; c=dp[n].sc; if(c<=d) { zz=md; zm=sm; rh=md-1; } else { lh=md+1; } } return zm-zz*d; }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:92:15: warning: 'zm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |  return zm-zz*d;
      |               ^
aliens.cpp:92:14: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |  return zm-zz*d;
      |            ~~^~
#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...