Submission #720175

#	Time	Username	Problem	Language	Result	Execution time	Memory
720175		Cyanmond	Feast (NOI19_feast)	C++17	100 / 100	658 ms	36176 KiB

feast

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf = 1ll << 55;

using D = std::array<std::array<std::vector<i64>, 2>, 2>;

std::vector<i64> mergeConcave(const std::vector<i64> &a, const std::vector<i64> &b) {
    const int sl = (int)a.size(), sr = (int)b.size();
    std::vector<i64> ret(sl + sr - 1);
    int j = 1;
    i64 val = a[0] + b[0];
    ret[0] = val;
    for (int i = 1; i < sl; ++i) {
        while (j != sr and b[j] - b[j - 1] > a[i] - a[i - 1]) {
            val += b[j] - b[j - 1];
            ret[i - 1 + j] = val;
            ++j;
        }
        val += a[i] - a[i - 1];
        ret[i + j - 1] = val;
    }
    while (j != sr) {
        val += b[j] - b[j - 1];
        ret[sl - 1 + j] = val;
        ++j;
    }
    return ret;
}
void chmax(std::vector<i64> &a, const std::vector<i64> &b) {
    const int n = (int)std::min(a.size(), b.size());
    for (int i = 0; i < n; ++i) a[i] = std::max(a[i], b[i]);
}
void chmax(i64 &a, const i64 b) {
    if (a < b) a = b;
}

void solve() {
    int N, K;
    std::cin >> N >> K;
    std::vector<i64> A(N);
    for (auto &e : A) std::cin >> e;

    auto merge = [&](const D &dl, const D &dr) {
        const int sl = (int)dl[0][0].size(), sr = (int)dr[0][0].size();
        D ret;
        for (int x = 0; x < 2; ++x) {
            for (int y = 0; y < 2; ++y) {
                ret[x][y].assign(sl + sr - 1, -inf);
            }
        }
        for (int xl = 0; xl < 2; ++xl) {
            for (int xr = 0; xr < 2; ++xr) {
                for (int yl = 0; yl < 2; ++yl) {
                    for (int yr = 0; yr < 2; ++yr) {
                        // merge !
                        // ret[xl][yr] <- dl[xl][xr] * dr[yl][yr]
                        const auto &a = dl[xl][xr], &b = dr[yl][yr];
                        auto &res = ret[xl][yr];
                        if (xr == 1 and yl == 1) {
                            const auto &lVec = dl[xl][xr], &rVec = dr[yl][yr];
                            auto mVec = mergeConcave(lVec, rVec);
                            mVec.erase(mVec.begin());
                            mVec[0] = -inf;
                            chmax(ret[xl][yr], mVec);
                            /*
                            int j = 1;
                            i64 val = a[0] + b[0];
                            // chmax(res[0], val);
                            for (int i = 1; i < sl; ++i) {
                                while (j != sr and b[j] - b[j - 1] > a[i] - a[i - 1]) {
                                    val += b[j] - b[j - 1];
                                    chmax(res[i - 1 + j - 1], val);
                                    ++j;
                                }
                                val += a[i] - a[i - 1];
                                chmax(res[i + j - 1 - 1], val);
                            }
                            while (j != sr) {
                                val += b[j] - b[j - 1];
                                chmax(res[sl - 1 + j - 1], val);
                                ++j;
                            }
                            res[0] = -inf;
                            */
                        } else {
                            int j = 1;
                            i64 val = a[0] + b[0];
                            chmax(res[0], val);
                            for (int i = 1; i < sl; ++i) {
                                while (j != sr and b[j] - b[j - 1] > a[i] - a[i - 1]) {
                                    val += b[j] - b[j - 1];
                                    chmax(res[i - 1 + j], val);
                                    ++j;
                                }
                                val += a[i] - a[i - 1];
                                chmax(res[i + j - 1], val);
                            }
                            while (j != sr) {
                                val += b[j] - b[j - 1];
                                chmax(res[sl - 1 + j], val);
                                ++j;
                            }
                        }
                    }
                }
            }
        }
        for (int x = 0; x < 2; ++x) {
            for (int y = 0; y < 2; ++y) {
                for (int i = 1; i < sl + sr - 1; ++i) {
                    ret[x][y][i] = std::max(ret[x][y][i], ret[x][y][i - 1]);
                }
            }
        }
        chmax(ret[0][0], ret[0][1]);
        chmax(ret[1][0], ret[1][1]);
        chmax(ret[0][0], ret[1][0]);
        chmax(ret[0][1], ret[1][1]);
        return ret;
    };

    auto solve = [&](auto &&self, const int l, const int r) -> D {
        if (r - l == 1) {
            D ret;
            ret[0][0] = {0, A[l]};
            ret[0][1] = {-inf, A[l]};
            ret[1][0] = {-inf, A[l]};
            ret[1][1] = {-inf, A[l]};
            return ret;
        }
        const int m = (l + r) / 2;
        const auto lRes = self(self, l, m), rRes = self(self, m, r);
        const auto ret = merge(lRes, rRes);
        return ret;
    };

    const auto res = solve(solve, 0, N);
    i64 answer = res[0][0][K];
    std::cout << answer << std::endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29