fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     // Tối ưu hóa I/O
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.  
  12.     int N;
  13.     if (!(cin >> N)) return 0;
  14.  
  15.     // Lưu trữ tọa độ đã chuyển đổi (U, V)
  16.     vector<pair<long long, long long>> apples(N);
  17.     for (int i = 0; i < N; ++i) {
  18.         long long t, x;
  19.         cin >> t >> x;
  20.         apples[i] = {t - x, t + x};
  21.     }
  22.  
  23.     // Sắp xếp U tăng dần, U bằng nhau thì V tăng dần
  24.     sort(apples.begin(), apples.end());
  25.  
  26.     // Tìm độ dài Longest Strictly Decreasing Subsequence của V
  27.     // Bằng cách tìm Longest Strictly Increasing Subsequence của -V
  28.     vector<long long> dp;
  29.     for (int i = 0; i < N; ++i) {
  30.         long long v = -apples[i].second;
  31.  
  32.         auto it = lower_bound(dp.begin(), dp.end(), v);
  33.         if (it == dp.end()) {
  34.             dp.push_back(v);
  35.         } else {
  36.             *it = v;
  37.         }
  38.     }
  39.  
  40.     // Kết quả là độ dài của LDS
  41.     cout << dp.size() << "\n";
  42.  
  43.     return 0;
  44. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
8
10 4
4 2
7 10
5 3
1 9
0 6
3 8
0 9
stdout
copy 
2
https://ideone.com/CweZMn
language:
C++14 (gcc 8.3)
created:
1 hour 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!