Submission #702052

#	Time	Username	Problem	Language	Result	Execution time	Memory
702052		Cyanmond	Holiday (IOI14_holiday)	C++17	24 / 100	5090 ms	8716 KiB

holiday

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

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

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 = nrRes;
        }

        std::sort(A.begin() + l, A.begin() + m, std::greater());
        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 = conv(lRes, rRes);

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

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