Submission #1674856

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

using int64 = long long;

const int64 MINIMIZE = -45141919810364364LL;

// 最大値を計算するSegment tree
template <typename T>
struct SegmentTree {
    const T DEFULT_VAL = MINIMIZE;

    vector<T> dat;
    int end;

    SegmentTree(vector<T>& d) {
        int n = d.size();
        end = 1;
        while (end < n) end *= 2;

        dat.resize(2 * end - 1, DEFULT_VAL);
        
        for (int i = 0; i < d.size(); i++) {
            dat[i + end - 1] = d[i];
        }
        for (int i = end - 2; i >= 0; i--) {
            dat[i] = max(dat[2 * i + 1], dat[2 * i + 2]);
        }
    }

    void update(int idx, T a) {
        int id = idx + end - 1;
        dat[id] = a;
        while (id > 0) {
            id = (id - 1) / 2;
            dat[id] = max(dat[id * 2 + 1], dat[id * 2 + 2]);
        }
    }

    T query(int lb, int ub) {
        return query(lb, ub, 0, 0, end);
    }

    T query(int lb, int ub, int id, int node_lb, int node_ub) {
        if (node_ub <= lb || ub <= node_lb) { return DEFULT_VAL; }

        if (lb <= node_lb && node_ub <= ub) { return dat[id]; }
        else {
            T vl = query(lb, ub, id * 2 + 1, node_lb, (node_lb + node_ub) / 2),
              vr = query(lb, ub, id * 2 + 2, (node_lb + node_ub) / 2, node_ub);
            return max(vl, vr);
        }
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    vector<int64> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<int64> elts(N + 1, MINIMIZE);
    elts[0] = 0;

    SegmentTree<int64> segtree(elts);
    int64 ans = 0;
    for (int i = 0; i < K; i++) {
        for (int j = N; j >= 1; j--) {
            int64 res = segtree.query(max(0, j - M), j);
            segtree.update(j, res + A[j - 1] * (i + 1));
            ans = max(ans, res + A[j - 1] * (i + 1));

            /*
            if (res + A[j - 1] * (i + 1) >= 0) {
                cerr << "i: " << i << " j: " << j << " result: " << res + A[j - 1] * (i + 1) << endl;
            }
            */
        }
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result