Submission #39075029

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const int mod = 998244353;
const int N = 1e5 + 10;
#define endl '\n'

struct seg
{
#define ls (u << 1)
#define rs (ls | 1)
#define mid ((l + r) >> 1)
#define lson ls,l,mid
#define rson rs,mid+1,r
    struct info
    {
        i64 mx;
        info(){mx = 0;}
        info operator+(const info &a) const
        {
            info b;
            b.mx = max(mx, a.mx);
            return b;
        }
    };
    vector<info> tr;
    seg(int n) : tr((n << 2) + 10){};
    void pushup(int u) { tr[u] = tr[ls] + tr[rs]; }
    void modify(int u,int l,int r,int L,int R, i64 x){
        if(l>R||r<L)return;
        if(l>=L&&r<=R){
            tr[u].mx = x;
            return;
        }
        modify(lson,L,R,x),modify(rson,L,R,x);
        pushup(u);
    }
    i64 query(int u,int l,int r,int L,int R){
        if(l>R||r<L)return 0;
        if(l>=L&&r<=R)return tr[u].mx;
        return max(query(lson,L,R),query(rson,L,R));
    }
};

void solve()
{
    int n;
    cin >> n;
    vector<i64> h(n + 1), a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    seg t(n);
    i64 mx = 0;
    for(int i = 1; i <= n; i++){
        i64 sum = t.query(1, 1, n, 1, h[i]) + a[i];
        mx = max(mx, sum);
        t.modify(1, 1, n, h[i], h[i], sum);
    }
    cout << mx << endl;
}
int main()
{
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#endif
    int _ = 1;
    //cin >> _;
    while (_--)
        solve();
}

Submission Info

Judge Result