1. #include <bits/stdc++.h>
2. #include "aliens.h"
3. #define ff first
4. #define ss second
5. using namespace std;
6.
7. long long take_photos(int N, int R, int K, vector<int> x, vector<int> y) {
8. vector< pair<int,int> > Iall(N);
9. for(int i =0; i < N; i++) {
10. Iall[i].ff =min(x[i],y[i]);
11. Iall[i].ss =max(x[i],y[i])+1;}
12. sort(begin(Iall),end(Iall));
13. vector< pair<int,int> > I;
14. int rp =-1;
15. for(int i =0; i < N; i++) {
16. if(i < N-1 && Iall[i].ff == Iall[i+1].ff) continue;
17. if(Iall[i].ss <= rp) continue;
18. I.push_back(Iall[i]);
19. rp =Iall[i].ss;}
20. N =I.size();
21. K =min(K,N);
22.
23. long long ans =1e18;
24. long long costA =-1, costB =1e13;
25. while(costB-costA > 1) {
26. long long cost =(costA+costB)/2;
27. vector<long long> A(N+1,1e18);
28. vector<int> curK(N+1,0);
29. A[0] =0;
30. vector< pair<long long,int> > q;
31. int a =-1;
32. for(int i =0; i < N; i++) {
33. long long x =A[i]+1LL*I[i].ff*I[i].ff, y =2*I[i].ff;
34. while(q.size() >= 2) {
35. long long x2 =q.back().ff, y2 =2*I[q.back().ss].ff;
36. long long x1 =q[q.size()-2].ff, y1 =2*I[q[q.size()-2].ss].ff;
37. if(1.0*(x2-x1)/(y2-y1) > 1.0*(x-x2)/(y-y2)) q.pop_back();
38. else break;}
39. a =min(a,(int)q.size()-1);
40. q.push_back(make_pair(x,i));
41. if(a == -1) a++;
42. while(a < (int)q.size()-1) {
43. if(q[a].ff-2LL*I[q[a].ss].ff*I[i].ss >= q[a+1].ff-2LL*I[q[a+1].ss].ff*I[i].ss) a++;
44. else break;}
45. A[i+1] =q[a].ff-2LL*I[q[a].ss].ff*I[i].ss+1LL*I[i].ss*I[i].ss+cost;
46. curK[i+1] =curK[q[a].ss]+1;
47. if(i < N-1 && I[i+1].ff < I[i].ss)
48. A[i+1] -=1LL*(I[i].ss-I[i+1].ff)*(I[i].ss-I[i+1].ff);
49. }
50. if(curK[N] >= K) {
51. costA =cost;
52. ans =A[N]-K*cost;}
53. else costB =cost;}
54.
55. return ans;}
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.cpp:2:20: fatal error: aliens.h: No such file or directory
compilation terminated.
stdout
Standard output is empty