Submission #405950

#TimeUsernameProblemLanguageResultExecution timeMemory
405950cgiosyAliens (IOI16_aliens)C++17
0 / 100
1 ms204 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; } }; ll pw(int x) { return ll(x)*x; } ll take_photos(int N, int M, int K, vector<int> L, vector<int> R) { lr A[N]; for(int i=0; i<N; i++) { int x=L[i], y=R[i]; A[i]={min(x, y), max(x, y)}; } 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); auto f=[&](ll m, int k=INT_MAX) { ll C[N+1]; int D[N+1]; C[0]=D[0]=0; for(int i=1; i<=N; i++) { C[i]=LLONG_MAX; for(int j=0; j<i; j++) { ll x=C[j]+pw(A[i-1].r-A[j].l+1)-pw(max(A[i].l-A[j].r, 0))-m; if(x<C[i]) C[i]=x, D[i]=D[j]+1; } if(D[i]>k) return ll(-1); } return C[N]; }; ll l=-pw(M), r=pw(M); 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:38:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   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...