\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-forces>}}\)

• Thử hết tất cả các dãy và kiểm tra nếu nó hợp lệ thì lấy tổng, chọn dãy có tổng lớn nhất

** Nếu bạn muốn hướng dẫn trâu (recursive, bitmasking) thì hãy comment bên dưới để mình expand editorial **

\(\color{orange}{\text{Hint 2 <Dynamic-prgramming>}}\)

• Gọi \(f[]\) là mảng nguyên \((init = 0, size = max\_val)\), mà ở đó \(f[x]\) chỉ tổng giá trị tối ưu nhất với giá trị tối đa tại đó là \(x\)

Khi \(s_i = 1\), bài toán quy về dạng \(Maximum Sum Increasing Subsequences\)

Gọi \(v = c_{i, 0}\) là giá trị của ngày đó

Lúc này ta duyệt với mọi ngày \(p\) và \(0 \leq p \leq v\) và thêm giá trị vào

Sau đó ta chỉ cần tìm vị trí có giá trị tối ưu nhất

** Nếu bạn muốn xem code hãy comment bên dưới để mình expand editorial **

\(\color{orange}{\text{Hint 3 <Data Structure>}}\)

• Nhận xét cách trên ta phải duyệt hết các gía trị mà ta biết chắc nó không tối ưu, ta sẽ cập nhật trước

Ta chỉ cần tìm trong các ngày \(p\) và \(0 \leq p \leq v\) mà \(f[x]\) đạt giá trị tối đa để có thể chèn thêm giá trị \(v\) vào

Sau đó cập nhật kết quả \(f[p]\) cho các ngày \(p \geq v\) để lần sau có thể tìm được giá trị tối ưu

Gọi \(getMax(p)\) là giá trị tối ưu cần tìm trong các ngày \(p\) trước \(v\), ta sẽ gọi \(getMax(v)\)

Gọi \(update(p, v)\) là việc ta cập nhật giá trị \(v\) cho các ngày \(p\) sau \(v\), ta sẽ gọi \(update(p, f[v] + v)\)

Ta cần kiếm cách cài đặt \(getMax(x)\) và \(update(p, v)\) tối ưu nhất

** Nếu bạn muốn xem code hãy comment bên dưới để mình expand editorial **

\(\color{orange}{\text{Hint 4 <Memory Optimization>}}\)

• Chúng ta có thể không cần lưu mảng nhận mà có thể giải trực tiếp từng ngày và liên tục cập nhật giá trị \(res\) tối ưu

\(\color{green}{\text{Preference Code }}\): Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n \times (O(getMax()) + O(update())))\ \color{purple}{\text{time}}\ ||\ O(max\_val)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int res = 0;
    for (int n = readInt(); n--; ) {
        int x;
        cin >> x;

        update(x, getMax(x) + x);
        maximize(res, f[x]);
    }

    cout << res;
    return 0;
}

\(\color{orange}{\text{Hint 5 <Fenwick Tree>}}\)

• Sử dụng cấu trúc dữ liệu Fenwick Tree (a.k.a BIT - Binary Indexed Tree)

\(getMax(p)\) sẽ chạy trong \(O(\log BIT.size) = O(\log f.size) = O(\log max\_val)\) (hàm kiểm tra \(O(max(a, b)) = O(1)\))

\(update(p, v)\) sẽ chạy trong \(O(\log BIT.size) = O(\log f.size) = O(\log max\_val)\) (hàm kiểm tra \(O(max(a, b)) = O(1)\))

** Nếu bạn thấy khó hiểu, hãy comment bên dưới và mình sẽ expand editorial để chi tiết vấn đề hơn**

\(\color{green}{\text{Preference Code }}\): Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n \times \log max\_val)\ \color{purple}{\text{time}}\ ||\ O(max\_val)\ \color{purple}{\text{memory}}}}\)

int BIT[LIM + 1] = {};
void update(int p, int v) {
    for (; p < LIM; p += p & -p)
        maximize(BIT[p], v);
}

int getMax(int p) {
    int res = 0;
    for (; p > 0; p -= p & -p)
        maximize(res, BIT[p]);

    return res;
}

int main()
{
    int res = 0;
    for (int n = readInt(); n--; ) {
        int x;
        cin >> x;

        update(x, getMax(x) + x);
        maximize(res, f[x]);
    }

    cout << res;
    return 0;
}

\(\color{orange}{\text{Hint 6 <Unnamed Method>}}\)

• Trong trường hợp tổng quát khi \(s_i \neq 1\), bạn có thể giải nó nhưng độ phức tạp sẽ rất lớn hoặc phức tạp để giải

Bạn cần hai mảng là mảng hiện tại và mảng trước đó

Bạn cần phải cập nhật toàn bộ mảng để có thể tính toán tiếp

** Comment bên dưới nếu bạn muốn expand editorial **

• Mình sẽ dụng một kĩ thuật không tên này có thể giúp bạn giải quyết điều đó: Mình sẽ cập nhật liên tục sao cho lần lấy giá trị trước ko ảnh hưởng tới lần sau cùng ngày

Mình sẽ sort mảng giảm dần và loại bỏ các phần tử trùng nhau (vì trùng nhau cũng ra kết quả như thế)

Mình sẽ cập nhật và lấy giá trị của các số từ lớn đến bé

Hàm \(update(p, v)\) chỉ cập nhật các \(p \geq v\)

Hàm \(getMax(p)\) chỉ cập nhật các \(p \leq v\)

Lần cập nhật sau giá trị \(x < v\) sẽ là \(p \geq v > v\) nên nó sẽ không cập nhật lên phía trước

Lần lấy giá trị sau \(x < v\) sẽ là \(p \leq x < v\) nên nó sẽ không ảnh hưởng giá trị hiện tại

\(\color{green}{\text{Preference AC Code }}\): Online Solving, Data Structure (Fenwick Tree)

\(^{^{\color{purple}{\text{Complexity : }} O(n \times m \log m \times \log max\_val)\ \color{purple}{\text{time}}\ ||\ O(max\_val)\ \color{purple}{\text{memory}}}}\)

int BIT[LIM + 1] = {};
void update(int p, int v) {
    for (; p < LIM; p += p & -p)
        maximize(BIT[p], v);
}

int getMax(int p) {
    int res = 0;
    for (; p > 0; p -= p & -p)
        maximize(res, BIT[p]);

    return res;
}

int main()
{
    int res = 0;
    for (int n = readInt(); n--; ) {
        set<int, greater<int> > S;
        for (int m = readInt(); m--; S.insert(readInt()));
        for (int x : S) {
            BIT[x] = getMax(x) + x;
            update(x, BIT[x]);
            maximize(res, BIT[x]);
        }
    }

    cout << res;
    return 0;
}