Submission #406077

#TimeUsernameProblemLanguageResultExecution timeMemory
406077cgiosyAliens (IOI16_aliens)C++17
100 / 100
100 ms4804 KiB
#include <bits/stdc++.h> using namespace std; using ll=long long; struct lr { int l, r; bool operator<(lr b) const { return l<b.l; } }; struct point { ll a, b; ll operator()(ll x) const { return a*x+b; } }; ll ccw(point& o, point& p, point& q) { return (o.a-p.a)*(o.b-q.b)-(o.b-p.b)*(o.a-q.a); } ll pw(ll x) { return x*x; } ll take_photos(int N, int M, int K, vector<int> L, vector<int> R) { lr A[N+1]; for(int i=0; i<N; i++) { int x=L[i], y=R[i]; A[i]={min(x, y), max(x, y)+1}; } sort(A, A+N); int N2=0; for(int i=1; i<N; i++) if(A[N2].r<A[i].r) A[N2+=A[N2].l<A[i].l]=A[i]; K=min(K, N=N2+1); point H[N+1]; int D[N+1]; A[N].l=A[N-1].r; auto f=[&](ll m, int k=INT_MAX) { int s=0, e=0; H[0]={-2*A[0].l, pw(A[0].l)}; D[0]=0; for(int i=0; i<N; i++) { ll l=A[i+1].l, r=A[i].r; while(s<e && H[s](r)>H[s+1](r)) s++; point p{-2*l, H[s](r) + pw(l)+pw(r)-pw(max(r-l, 0LL)) - m}; while(s<e && ccw(H[e-1], H[e], p)>=0) e--; H[++e]=p; D[e]=D[s]+1; if(D[e]>k) return ll(-1); } return H[e].b-pw(A[N].l); }; ll l=-pw(M), r=0; while(l<r) { ll m=l+r+1>>1; if(~f(m, K)) l=m; else r=m-1; } return f(r)+K*r; }

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:50:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   ll m=l+r+1>>1;
      |        ~~~^~
#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...