oj.uz

Submission #720159

# Submission time Handle Problem Language Result Execution time Memory
720159 2023-04-07T14:03:23 Z Cyanmond Feast (NOI19_feast) C++17
30 / 100
 800 ms 36000 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 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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 34968 KB Output is correct
2 Correct 561 ms 35264 KB Output is correct
3 Correct 569 ms 34520 KB Output is correct
4 Correct 577 ms 35560 KB Output is correct
5 Correct 562 ms 32320 KB Output is correct
6 Correct 559 ms 32364 KB Output is correct
7 Correct 538 ms 31316 KB Output is correct
8 Correct 572 ms 35700 KB Output is correct
9 Correct 544 ms 32476 KB Output is correct
10 Correct 553 ms 31448 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 31724 KB Output is correct
2 Correct 551 ms 33340 KB Output is correct
3 Correct 539 ms 32312 KB Output is correct
4 Correct 556 ms 33088 KB Output is correct
5 Correct 547 ms 31000 KB Output is correct
6 Correct 533 ms 32584 KB Output is correct
7 Correct 547 ms 35420 KB Output is correct
8 Correct 552 ms 35384 KB Output is correct
9 Correct 548 ms 32348 KB Output is correct
10 Correct 548 ms 32100 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 32856 KB Output is correct
2 Correct 779 ms 33080 KB Output is correct
3 Correct 797 ms 36000 KB Output is correct
4 Correct 785 ms 31700 KB Output is correct
5 Correct 789 ms 32356 KB Output is correct
6 Correct 787 ms 35240 KB Output is correct
7 Correct 800 ms 32276 KB Output is correct
8 Correct 790 ms 33060 KB Output is correct
9 Correct 789 ms 32024 KB Output is correct
10 Correct 785 ms 33000 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 0 ms 212 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 0 ms 212 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 558 ms 34968 KB Output is correct
2 Correct 561 ms 35264 KB Output is correct
3 Correct 569 ms 34520 KB Output is correct
4 Correct 577 ms 35560 KB Output is correct
5 Correct 562 ms 32320 KB Output is correct
6 Correct 559 ms 32364 KB Output is correct
7 Correct 538 ms 31316 KB Output is correct
8 Correct 572 ms 35700 KB Output is correct
9 Correct 544 ms 32476 KB Output is correct
10 Correct 553 ms 31448 KB Output is correct
11 Correct 545 ms 31724 KB Output is correct
12 Correct 551 ms 33340 KB Output is correct
13 Correct 539 ms 32312 KB Output is correct
14 Correct 556 ms 33088 KB Output is correct
15 Correct 547 ms 31000 KB Output is correct
16 Correct 533 ms 32584 KB Output is correct
17 Correct 547 ms 35420 KB Output is correct
18 Correct 552 ms 35384 KB Output is correct
19 Correct 548 ms 32348 KB Output is correct
20 Correct 548 ms 32100 KB Output is correct
21 Correct 784 ms 32856 KB Output is correct
22 Correct 779 ms 33080 KB Output is correct
23 Correct 797 ms 36000 KB Output is correct
24 Correct 785 ms 31700 KB Output is correct
25 Correct 789 ms 32356 KB Output is correct
26 Correct 787 ms 35240 KB Output is correct
27 Correct 800 ms 32276 KB Output is correct
28 Correct 790 ms 33060 KB Output is correct
29 Correct 789 ms 32024 KB Output is correct
30 Correct 785 ms 33000 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 1 ms 212 KB Output isn't correct
33 Halted 0 ms 0 KB -