oj.uz

Submission #720171

# Submission time Handle Problem Language Result Execution time Memory
720171 2023-04-07T14:13:20 Z Cyanmond Feast (NOI19_feast) C++17
4 / 100
 591 ms 35076 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 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) {
                            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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 30464 KB Output is correct
2 Correct 474 ms 31708 KB Output is correct
3 Correct 480 ms 34992 KB Output is correct
4 Correct 469 ms 32032 KB Output is correct
5 Correct 503 ms 31776 KB Output is correct
6 Correct 468 ms 32300 KB Output is correct
7 Correct 456 ms 34936 KB Output is correct
8 Correct 463 ms 35076 KB Output is correct
9 Correct 445 ms 33152 KB Output is correct
10 Correct 465 ms 32840 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 32780 KB Output is correct
2 Correct 463 ms 32928 KB Output is correct
3 Incorrect 439 ms 31316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 591 ms 31016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 30464 KB Output is correct
2 Correct 474 ms 31708 KB Output is correct
3 Correct 480 ms 34992 KB Output is correct
4 Correct 469 ms 32032 KB Output is correct
5 Correct 503 ms 31776 KB Output is correct
6 Correct 468 ms 32300 KB Output is correct
7 Correct 456 ms 34936 KB Output is correct
8 Correct 463 ms 35076 KB Output is correct
9 Correct 445 ms 33152 KB Output is correct
10 Correct 465 ms 32840 KB Output is correct
11 Correct 469 ms 32780 KB Output is correct
12 Correct 463 ms 32928 KB Output is correct
13 Incorrect 439 ms 31316 KB Output isn't correct
14 Halted 0 ms 0 KB -