fork download 
  1. /* Author haleyk10198 */
  2. #include <iostream>
  3. #include <fstream>
  4. #include <sstream>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <map>
  9. #include <queue>
  10. #include <cmath>
  11. #include <algorithm>
  12. #include <cstring>
  13. #include <iomanip>
  14. #include <ctime>
  15. #include <string>
  16. #include <set>
  17.  
  18. #define E9 1000000000
  19. #define INF 2147483647
  20. #define PI 3.14159
  21. #define ll long long
  22. #define pii pair<int,int>
  23.  
  24. using namespace std;
  25.  
  26. vector<pii> arr;
  27.  
  28. int bins(int left,int right,int val){
  29. 	//classic binary search to find the last undestroyed beacon
  30. 	int mid=(left+right)>>1;
  31. 	if(arr[mid].first<val&&arr[mid+1].first>=val)
  32. 		return mid;
  33. 	else if(arr[mid].first>=val)
  34. 		return bins(left,mid-1,val);
  35. 	else
  36. 		return bins(mid+1,right,val);
  37. }
  38.  
  39. int main(){
  40. 	int n;
  41. 	scanf("%d",&n);
  42. 	for(int i=0;i<n;i++){
  43. 		int a,b;
  44. 		scanf("%d%d",&a,&b);
  45. 		arr.push_back(pii(a,b));
  46. 	}
  47. 	sort(arr.begin(),arr.end());
  48. 	int dp[n][2]; //state 0:off state1: on
  49. 	for(int i=0;i<n;i++){
  50. 		dp[i][0]=0;
  51. 		dp[i][1]=1;
  52. 	}
  53. 	for(int i=1;i<n;i++){
  54. 		dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
  55. 		//if the beacon is not activated then take the max number of prev. positions
  56. 		if(arr[i].first-arr[i].second>arr[0].first){
  57. 			int prev=bins(0,n-1,arr[i].first-arr[i].second);
  58. 			dp[i][1]=dp[prev+1][0]+1;
  59. 			//if it is to be activated then add it by finding the last undestroyed beacon
  60. 		}
  61. 	}
  62. 	printf("%d\n",n-max(dp[n-1][0],dp[n-1][1]));
  63. 	return 0;
  64. }
  65.  
Time limit exceeded #stdin #stdout 5s 134528KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/qlKrkI
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!