oj.uz

Submission #720155

# Submission time Handle Problem Language Result Execution time Memory
720155 2023-04-07T13:58:57 Z Cyanmond Feast (NOI19_feast) C++17
30 / 100
 915 ms 38820 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);
                        }
                    }
                }
            }
        }
        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 a = 0; a < 2; ++a) {
        for (int b = 0; b < 2; ++b) {
            answer = std::max(answer, res[a][b][K]);
        }
    }
    std::cout << answer << std::endl;
}

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 37456 KB Output is correct
2 Correct 557 ms 37848 KB Output is correct
3 Correct 582 ms 37088 KB Output is correct
4 Correct 588 ms 38156 KB Output is correct
5 Correct 563 ms 34960 KB Output is correct
6 Correct 557 ms 34916 KB Output is correct
7 Correct 564 ms 33892 KB Output is correct
8 Correct 559 ms 38320 KB Output is correct
9 Correct 570 ms 35024 KB Output is correct
10 Correct 573 ms 33996 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 32592 KB Output is correct
2 Correct 585 ms 34156 KB Output is correct
3 Correct 551 ms 33236 KB Output is correct
4 Correct 540 ms 34072 KB Output is correct
5 Correct 572 ms 33476 KB Output is correct
6 Correct 549 ms 33512 KB Output is correct
7 Correct 565 ms 36236 KB Output is correct
8 Correct 574 ms 38012 KB Output is correct
9 Correct 619 ms 34784 KB Output is correct
10 Correct 576 ms 32992 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 35516 KB Output is correct
2 Correct 861 ms 35740 KB Output is correct
3 Correct 817 ms 38820 KB Output is correct
4 Correct 799 ms 34340 KB Output is correct
5 Correct 862 ms 35000 KB Output is correct
6 Correct 901 ms 38044 KB Output is correct
7 Correct 915 ms 35372 KB Output is correct
8 Correct 850 ms 36060 KB Output is correct
9 Correct 837 ms 34988 KB Output is correct
10 Correct 831 ms 36036 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 37456 KB Output is correct
2 Correct 557 ms 37848 KB Output is correct
3 Correct 582 ms 37088 KB Output is correct
4 Correct 588 ms 38156 KB Output is correct
5 Correct 563 ms 34960 KB Output is correct
6 Correct 557 ms 34916 KB Output is correct
7 Correct 564 ms 33892 KB Output is correct
8 Correct 559 ms 38320 KB Output is correct
9 Correct 570 ms 35024 KB Output is correct
10 Correct 573 ms 33996 KB Output is correct
11 Correct 563 ms 32592 KB Output is correct
12 Correct 585 ms 34156 KB Output is correct
13 Correct 551 ms 33236 KB Output is correct
14 Correct 540 ms 34072 KB Output is correct
15 Correct 572 ms 33476 KB Output is correct
16 Correct 549 ms 33512 KB Output is correct
17 Correct 565 ms 36236 KB Output is correct
18 Correct 574 ms 38012 KB Output is correct
19 Correct 619 ms 34784 KB Output is correct
20 Correct 576 ms 32992 KB Output is correct
21 Correct 822 ms 35516 KB Output is correct
22 Correct 861 ms 35740 KB Output is correct
23 Correct 817 ms 38820 KB Output is correct
24 Correct 799 ms 34340 KB Output is correct
25 Correct 862 ms 35000 KB Output is correct
26 Correct 901 ms 38044 KB Output is correct
27 Correct 915 ms 35372 KB Output is correct
28 Correct 850 ms 36060 KB Output is correct
29 Correct 837 ms 34988 KB Output is correct
30 Correct 831 ms 36036 KB Output is correct
31 Correct 1 ms 312 KB Output is correct
32 Incorrect 1 ms 212 KB Output isn't correct
33 Halted 0 ms 0 KB -