oj.uz

Submission #720164

# Submission time Handle Problem Language Result Execution time Memory
720164 2023-04-07T14:06:04 Z Cyanmond Feast (NOI19_feast) C++17
0 / 100
 38 ms 5080 KB 
#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 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]
                        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);
                        } else {
                            const auto &lVec = dl[xl][xr], &rVec = dr[yl][yr];
                            const auto mVec = mergeConcave(lVec, rVec);
                            chmax(ret[xl][yr], mVec);
                        }
                    }
                }
            }
        }
        for (int x = 0; x < 4; ++x) {
            for (int y = 0; y < 4; ++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 = -inf;
    for (int i = 0; i <= K; ++i) answer = std::max(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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 5068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 5056 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 5080 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 5068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -