fork download
copy 
  1. #include <bits/stdc++.h>                                                                                                                                                                                      //Logm
  2. using namespace std;
  3. #define int long long
  4.  
  5. const int N = 1e5+5;
  6. int n, a[N];
  7.  
  8. vector<int> val;
  9. int comp[N];
  10.  
  11. int bit[N];
  12. void update(int i, int val) { // dp[i] = val
  13.     for (; i < N; i += i & -i)
  14.         bit[i] = max(bit[i], val);
  15. }
  16. int getmax(int i) { // lấy max(dp[1..i])
  17.     int res = 0;
  18.     for (; i > 0; i -= i & -i)
  19.         res = max(res, bit[i]);
  20.     return res;
  21. }
  22.  
  23. signed main() {
  24.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  25.     if (fopen("_ab.inp", "r")) {
  26.         freopen("_ab.inp", "r", stdin);
  27.         freopen("_ab.out", "w", stdout);
  28.     }
  29.  
  30.     cin >> n;
  31.     for (int i = 1; i <= n; ++i) {
  32.         cin >> a[i];
  33.         val.push_back(a[i]);
  34.     }
  35.     // sắp xếp tất cả giá trị và loại bỏ đi những giá trị trùng lặp
  36.     sort(val.begin(), val.end());
  37.     val.erase(unique(val.begin(), val.end()), val.end());
  38.     // {2, 10, 4, 5, 2, 4, 4} -> {2, 4, 5, 10}
  39.  
  40.     // lưu ý vì ctdl bit không thể update hay get ở vị trí 0
  41.     // nên cần +2 giá trị nén để không bị tràn
  42.     for (int i = 1; i <= n; ++i)
  43.         comp[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 2;
  44.     // a = {2, 10, 4, 5, 2, 4, 4}
  45.     // comp = {2, 5, 3, 4, 2, 3, 3}
  46.  
  47.     int ans = 0;
  48.     for (int i = 1; i <= n; ++i) {
  49.         int last = getmax(comp[i] - 1); // tìm dp[x] lớn nhất với x < a[i]
  50.         // vì ở đây lấy max có vị trí comp[i] - 1 nên comp[i] phải > 1
  51.         update(comp[i], last + a[i]); // thêm a[i] vào dp[x] lớn nhất và cập nhật cho dp[a[i]]
  52.         ans = max(ans, last + a[i]); // lấy max kết quả
  53.     }
  54.     cout << ans;
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tXYrMe
language:
C++14 (gcc 8.3)
created:
14 days 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!