oj.uz

Submission #702058

# Submission time Handle Problem Language Result Execution time Memory
702058 2023-02-22T14:48:07 Z Cyanmond Holiday (IOI14_holiday) C++17
100 / 100
 848 ms 32216 KB 
#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 = 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 = 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);
        }
        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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 30892 KB Output is correct
2 Correct 702 ms 31044 KB Output is correct
3 Correct 761 ms 31164 KB Output is correct
4 Correct 693 ms 31188 KB Output is correct
5 Correct 783 ms 29564 KB Output is correct
6 Correct 232 ms 9212 KB Output is correct
7 Correct 419 ms 16456 KB Output is correct
8 Correct 517 ms 19284 KB Output is correct
9 Correct 170 ms 6804 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1632 KB Output is correct
2 Correct 21 ms 1552 KB Output is correct
3 Correct 22 ms 1548 KB Output is correct
4 Correct 21 ms 1372 KB Output is correct
5 Correct 18 ms 1236 KB Output is correct
6 Correct 7 ms 980 KB Output is correct
7 Correct 7 ms 948 KB Output is correct
8 Correct 7 ms 864 KB Output is correct
9 Correct 7 ms 852 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 31400 KB Output is correct
2 Correct 803 ms 32216 KB Output is correct
3 Correct 360 ms 10672 KB Output is correct
4 Correct 20 ms 1216 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 8 ms 928 KB Output is correct
7 Correct 9 ms 852 KB Output is correct
8 Correct 825 ms 20492 KB Output is correct
9 Correct 848 ms 20320 KB Output is correct