Submission #946342

#	Time	Username	Problem	Language	Result	Execution time	Memory
946342		zwezdinv	Candies (JOI18_candies)	C++17	100 / 100	623 ms	15232 KiB

candies

#include<bits/stdc++.h>

const int N = 2e5;

int n;
int a[N];

std::vector<long long> merge(std::vector<long long> a_, std::vector<long long> b_) {
        int n = a_.size(), m = b_.size();
        std::vector<long long> a(n - 1), b(m - 1);
        for (int i = 0; i + 1 < n; ++i) {
                a[i] = a_[i + 1] - a_[i];
        }
        for (int i = 0; i + 1 < m; ++i) {
                b[i] = b_[i + 1] - b_[i];
        }
        std::vector<long long> c;
        std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c), std::greater<>());
        std::vector<long long> c_(c.size() + 1);
        c_[0] = a_[0] + b_[0];
        for (int i = 0; i < c.size(); ++i) {
                c_[i + 1] = c_[i] + c[i];
        }
        return c_;
}

std::vector<long long> mx(std::vector<long long> a, std::vector<long long> b) {
        std::vector<long long> res(std::max(a.size(), b.size()), LLONG_MIN);
        for (int i = 0; i < res.size(); ++i) {
                if (i < a.size()) res[i] = std::max(res[i], a[i]);
                if (i < b.size()) res[i] = std::max(res[i], b[i]);
        }
        return res;
}

std::array<std::array<std::vector<long long>, 2>, 2> dc(int l, int r) {
        std::array<std::array<std::vector<long long>, 2>, 2> res;
        if (l == r) {
                for (int x = 0; x < 2; ++x) {
                        for (int y = 0; y < 2; ++y) {
                                res[x][y] = {0};
                        }
                }
                res[1][1].push_back(a[l]);                
                // std::cout << l << ' ' << r << std::endl;
                // for (auto xx : res) {
                //         for (auto x : xx) {
                //                 for (auto i : x) std::cout << i << ' ';
                //                 std::cout << std::endl;
                //         }
                // }
                // std::cout << std::endl;
                return res;
        }
        int m = (l + r) / 2;
        auto left = dc(l, m), right = dc(m + 1, r);
        for (int x = 0; x < 2; ++x) {
                for (int y = 0; y < 2; ++y) {
                        for (int x_ = 0; x_ < 2; ++x_) {
                                for (int y_ = 0; y_ < 2; y_++) {
                                        if (y == 1 && x_ == 1) continue;
                                        res[x][y_] = mx(res[x][y_], merge(left[x][y], right[x_][y_]));
                                }
                        }
                }
        }
        // std::cout << l << ' ' << r << std::endl;
        // for (auto xx : res) {
        //         for (auto x : xx) {
        //                 for (auto i : x) std::cout << i << ' ';
        //                 std::cout << std::endl;
        //         }
        // }
        // std::cout << std::endl;
        return res;
}


int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        std::cin >> n;
        for (int i = 0; i < n; ++i) std::cin >> a[i];
        auto vc = dc(0, n - 1);
        std::vector<long long> res;
        for (int x = 0; x < 2; ++x) {
                for (int y = 0; y < 2; ++y) {
                        res = mx(res, vc[x][y]);
                }
        }
        for (int k = 1; k <= (n + 1) / 2; ++k) std::cout << res[k] << '\n';
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>)':
candies.cpp:21:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int i = 0; i < c.size(); ++i) {
      |                         ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<long long int> mx(std::vector<long long int>, std::vector<long long int>)':
candies.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 0; i < res.size(); ++i) {
      |                         ~~^~~~~~~~~~~~
candies.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 if (i < a.size()) res[i] = std::max(res[i], a[i]);
      |                     ~~^~~~~~~~~~
candies.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 if (i < b.size()) res[i] = std::max(res[i], b[i]);
      |                     ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92