fork(26) download
  1. #include <iostream>
  2. using namespace std;
  3. const int maxn = 1e6 + 5;
  4.  
  5. int n, b[maxn], dp[maxn];
  6.  
  7. int main() {
  8. ios_base::sync_with_stdio(0);
  9. cin.tie(NULL);
  10. cin >> n;
  11. for (int i = 0, a; i < n; i++) {
  12. cin >> a;
  13. cin >> b[a];
  14. }
  15. if (b[0] > 0) {
  16. dp[0] = 1;
  17. }
  18. int mx = 0;
  19. for (int i = 1; i < maxn; i++) {
  20. if (b[i] == 0) {
  21. dp[i] = dp[i - 1];
  22. } else {
  23. if (b[i] >= i) {
  24. dp[i] = 1;
  25. } else {
  26. dp[i] = dp[i - b[i] - 1] + 1;
  27. }
  28. }
  29. if (dp[i] > mx) {
  30. mx = dp[i];
  31. }
  32. }
  33. cout << n - mx << '\n';
  34. return 0;
  35. }
  36.  
Success #stdin #stdout 0.01s 11272KB
stdin
4
1 9
3 1
6 1
7 4
stdout
1