Advertisement
Josif_tepe

Untitled

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