Submission #702153

#	Time	Username	Problem	Language	Result	Execution time	Memory
702153		Cyanmond	Holiday (IOI14_holiday)	C++17	100 / 100	903 ms	31660 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>

using i64 = long long int;
constexpr i64 inf = 1ll << 50;

template <class F>
std::vector<int> smawk(int rs, int cs, const F &select) {
    auto solve = [&](auto &&self, std::vector<int> row, std::vector<int> col) -> std::vector<int> {
        const int n = (int)row.size();
        if (n == 0) {
            return {};
        }
        std::vector<int> c2, r2;
        for (const int i : col) {
            while ((not c2.empty()) and select(row[c2.size() - 1], c2.back(), i)) {
                c2.pop_back();
            }
            if ((int)c2.size() < n) {
                c2.push_back(i);
            }
        }
        for (int i = 1; i < n; i += 2) {
            r2.push_back(row[i]);
        }
        const auto a2 = self(self, r2, c2);
        std::vector<int> ret(n);
        for (int i = 0; i < (int)a2.size(); ++i) {
            ret[2 * i + 1] = a2[i];
        }

        int j = 0;
        for (int i = 0; i < n; i += 2) {
            ret[i] = c2[j];
            const int ed = i + 1 == n ? c2.back() : ret[i + 1];
            while (c2[j] != ed) {
                if (select(row[i], ret[i], c2[++j])) {
                    ret[i] = c2[j];
                }
            }
        }
        return ret;
    };
    std::vector<int> row(rs), col(cs);
    std::iota(row.begin(), row.end(), 0);
    std::iota(col.begin(), col.end(), 0);
    return solve(solve, row, col);
}
std::vector<i64> plusMaxConvolution(const std::vector<i64> a, const std::vector<i64> b) {
    const int n = (int)a.size(), m = (int)b.size();
    const auto get = [&](const int i, const int j) {
        return a[j] + b[i - j];
    };
    const auto select = [&](const int i, const int j, const int k) {
        if (i < k) {
            return false;
        }
        if (i - j >= m) {
            return true;
        }
        return get(i, j) <= get(i, k);
    };
    const auto amax = smawk(n + m - 1, n, select);
    std::vector<i64> ret(n + m - 1);
    for (int i = 0; i < n + m - 1; ++i) {
        ret[i] = get(i, amax[i]);
    }
    return ret;
}

std::vector<i64> conv(std::vector<i64> a, std::vector<i64> b) {
    const int n = (int)a.size(), m = (int)b.size();
    std::vector<i64> c(n + m - 1, -inf);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            c[i + j] = std::max(c[i + j], a[i] + b[j]);
        }
    }
    return c;
}

std::vector<i64> solveSub(std::vector<i64> A) {
    const int N = (int)A.size();
    auto divConq = [&](auto &&self, const int l, const int r) -> std::vector<i64> {
        if (r - l == 0) {
            std::vector<i64> ret = {0};
            return ret;
        }
        if (r - l == 1) {
            std::vector<i64> ret = {0, 0, A[l]};
            return ret;
        }
        const int m = (l + r) / 2;
        std::vector<i64> lResRec = self(self, l, m);
        std::vector<i64> rRes = self(self, m, r);
        {
            std::vector<i64> nrRes;
            for (int i = 0; i <= m - l; ++i) {
                nrRes.push_back(-inf);
            }
            std::copy(rRes.begin() + 1, rRes.end(), std::back_inserter(nrRes));
            rRes = std::move(nrRes);
        }

        std::vector<i64> lRes = {0};
        std::copy(A.begin() + l, A.begin() + m, std::back_inserter(lRes));
        for (int i = 1; i < (int)lRes.size(); ++i) {
            lRes[i] += lRes[i - 1];
        }
        const auto fullRes = plusMaxConvolution(rRes, lRes);

        std::vector<i64> res(std::max(fullRes.size(), lResRec.size()));
        for (int i = 0; i < std::max(fullRes.size(), lResRec.size()); ++i) {
            const auto a = i < fullRes.size() ? fullRes[i] : -inf;
            const auto b = i < lResRec.size() ? lResRec[i] : -inf;
            res[i] = std::max(a, b);
        }

        std::vector<i64> newA;
        std::merge(A.begin() + l, A.begin() + m, A.begin() + m, A.begin() + r, std::back_inserter(newA), std::greater());
        std::copy(newA.begin(), newA.end(), A.begin() + l);
        return res;
    };
    return divConq(divConq, 0, N);
}

i64 solve(int n, int start, int d, std::vector<i64> attraction) {
    std::vector<i64> lVec, rVec;
    for (int i = start - 1; i >= 0; --i) {
        lVec.push_back(attraction[i]);
    }
    for (int i = start; i < n; ++i) {
        rVec.push_back(attraction[i]);
    }

    auto calc1 = [](std::vector<i64> vec) {
        return solveSub(vec);
    };
    auto calc2 = [](std::vector<i64> vec) {
        std::vector<i64> vec2;
        for (const auto e : vec) {
            vec2.push_back(0);
            vec2.push_back(e);
        }
        return solveSub(vec2);
    };

    const auto l1 = calc1(lVec), l2 = calc2(lVec), r1 = calc1(rVec), r2 = calc2(rVec);

    i64 answer = 0;
    for (int i = 0; i <= d; ++i) {
        const int a = i;
        const int b = d - i + 2;
        answer = std::max(answer, l1[std::min((int)l1.size() - 1, a)] + r2[std::min((int)r2.size() - 1, b)]);
    }
    for (int i = 0; i <= d; ++i) {
        const int a = i;
        const int b = d - i + 1;
        answer = std::max(answer, l2[std::min((int)l2.size() - 1, a)] + r1[std::min((int)r1.size() - 1, b)]);
    }
    return answer;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    std::vector<i64> atr(n);
    for (int i = 0; i < n; ++i) {
        atr[i] = attraction[i];
    }
    return solve(n, start, d, atr);
}

Compilation message (stderr)

holiday.cpp: In lambda function:
holiday.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  113 |         for (int i = 0; i < std::max(fullRes.size(), lResRec.size()); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp:114:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             const auto a = i < fullRes.size() ? fullRes[i] : -inf;
      |                            ~~^~~~~~~~~~~~~~~~
holiday.cpp:115:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             const auto b = i < lResRec.size() ? lResRec[i] : -inf;
      |                            ~~^~~~~~~~~~~~~~~~
holiday.cpp: In instantiation of 'solveSub(std::vector<long long int>)::<lambda(auto:24&&, int, int)> [with auto:24 = solveSub(std::vector<long long int>)::<lambda(auto:24&&, int, int)>&]':
holiday.cpp:124:33:   required from here
holiday.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  113 |         for (int i = 0; i < std::max(fullRes.size(), lResRec.size()); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp:114:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             const auto a = i < fullRes.size() ? fullRes[i] : -inf;
      |                            ~~^~~~~~~~~~~~~~~~
holiday.cpp:115:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             const auto b = i < lResRec.size() ? lResRec[i] : -inf;
      |                            ~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53