Advertisement
Josif_tepe

Untitled

Apr 10th, 2023
688
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. //#include <bits/stdc++.h>
  5. using namespace std;
  6. typedef long long ll;
  7. const int maxn = 2e5 + 10;
  8. ll segment_tree[maxn * 3];
  9. void build(int L, int R, int pos) {
  10.     if(L == R) {
  11.         segment_tree[pos] = 0;
  12.     }
  13.     else {
  14.         int mid = (L + R) / 2;
  15.         build(L, mid, 2 * pos);
  16.         build(mid + 1, R, 2 * pos + 1);
  17.         segment_tree[pos] = max(segment_tree[2 * pos], segment_tree[2 * pos + 1]);
  18.     }
  19. }
  20. // L R   i L R j L R
  21. ll query(int L, int R, int pos, int i, int j) {
  22.     if(i <= L and R <= j) {
  23.         return segment_tree[pos];
  24.     }
  25.     if(R < i or j < L) {
  26.         return 0;
  27.     }
  28.     int mid = (L + R) / 2;
  29.     return max(query(L, mid, 2 * pos, i, j), query(mid + 1, R, 2 * pos + 1, i, j));
  30. }
  31. void update(int L, int R, int pos, int idx, ll new_val) {
  32.     if(L == R) {
  33.         segment_tree[pos] = new_val;
  34.         return;
  35.     }
  36.     int mid = (L + R) / 2;
  37.     if(idx <= mid) {
  38.         update(L, mid, 2 * pos, idx, new_val);
  39.     }
  40.     else {
  41.         update(mid + 1, R, 2 * pos + 1, idx, new_val);
  42.     }
  43.     segment_tree[pos] = max(segment_tree[2 * pos], segment_tree[2 * pos + 1]);
  44.  
  45. }
  46. int main() {
  47.     ios_base::sync_with_stdio(false);
  48.     int n;
  49.     cin >> n;
  50.     vector<int> h(n), a(n);
  51.     for(int i = 0; i < n; i++) {
  52.         cin >> h[i];
  53.     }
  54.     for(int i = 0; i < n; i++) {
  55.         cin >> a[i];
  56.     }
  57.     build(0, n + 1, 1);
  58.     for(int i = 0; i < n; i++) {
  59.         ll max_dp = query(0, n + 1, 1, 0, h[i]);
  60.         update(0, n + 1, 1, h[i], max_dp + a[i]);
  61.     }
  62.     cout << query(0, n + 1, 1, 0, n + 1) << endl;
  63.    
  64.     return 0;
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement