fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define PI acos(-1)
  5. #define hell 1000000007
  6. #define HELL 998244353
  7. #define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  8. #define fix(n) cout << fixed << setprecision(n)
  9. #define mset(a,n) memset(a,n,sizeof a)
  10. #define rep(i,a,b) for (__typeof((b)) i=(a);i<(b);i++)
  11. #define repp(i,a,b,p) for(__typeof((b)) i=(a);i<(b);i+=p)
  12. #define ren(i,a,b) for(__typeof((a)) i=(a);i>=(b);i--)
  13. #define renn(i,a,b,p) for(__typeof((a) i=(a);i>=(b);i-=p)
  14. #define ADD(a,b,c) ((a)%c+(b)%c)%c
  15. #define SUB(a,b,c) ((a)%c-(b)%c+c)%c
  16. #define MUL(a,b,c) (((a)%c)*((b)%c))%c
  17. #define lbd lower_bound
  18. #define ubd upper_bound
  19. #define ll long long
  20. #define ld long double
  21. #define pb push_back
  22. #define fi first
  23. #define se second
  24. #define vll vector<ll>
  25. #define pll pair<ll,ll>
  26. #define vpll vector<pll>
  27. #define all(v) (v).begin(), (v).end()
  28. #define sz(x) (ll)x.size()
  29. #define out(n) cout<<n<<" "
  30. #define outl(n) cout<<n<<endl
  31. #define line cout<<endl
  32. #define bug(n) {outl(n);return;}
  33. #define N 2505
  34. #define pii pair<int,int>
  35. #define M 1000000007
  36.  
  37. bool cmp(pll a,pll b){
  38. 	return a.first<b.first;
  39. }
  40.  
  41. void solve(){
  42. 	ll n;
  43. 	cin>>n;
  44. 	vector<pll> a(n);
  45. 	vector<ll> b(n);
  46. 	rep(i,0,n){
  47. 		cin>>a[i].first>>a[i].second;
  48. 		b[i]=a[i].first;
  49. 	}
  50. 	sort(b.begin(),b.end());
  51. 	sort(a.begin(),a.end(),cmp);
  52. 	vector<ll> dp(n+1,0);
  53. 	rep(i,1,n+1){
  54. 		ll inc = 1+ dp[i-1];
  55. 		ll temp = a[i-1].first-a[i-1].second;
  56. 		ll lb = lower_bound(b.begin(),b.end(),temp)-b.begin();
  57. 		ll exc=(i-lb-1)+dp[lb];
  58. 		dp[i]=min(inc,exc);
  59. 	}
  60. 	cout<<dp[n]<<endl;
  61.  
  62. }
  63.  
  64. int main(){
  65.     io;
  66.     ll t=1;
  67.     //cin>>t;
  68.     fix(12);
  69.     while(t--)
  70.         solve();
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
539
https://ideone.com/THbCLK
language:
C++14 (gcc 8.3)
created:
6 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!