fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:2:20: fatal error: aliens.h: No such file or directory
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/H320PF
IOI 2016 aliens
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!