oj.uz

Submission #946335

# Submission time Handle Problem Language Result Execution time Memory
946335 2024-03-14T13:56:12 Z Sokol080808 Candies (JOI18_candies) C++17
100 / 100
 605 ms 17060 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 5 ms 492 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 500 KB Output is correct
7 Correct 5 ms 600 KB Output is correct
8 Correct 8 ms 604 KB Output is correct
9 Correct 7 ms 600 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 6 ms 604 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 5 ms 604 KB Output is correct
15 Correct 5 ms 604 KB Output is correct
16 Correct 5 ms 604 KB Output is correct
17 Correct 5 ms 604 KB Output is correct
18 Correct 5 ms 604 KB Output is correct
19 Correct 5 ms 604 KB Output is correct
20 Correct 5 ms 604 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 5 ms 492 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 500 KB Output is correct
7 Correct 5 ms 600 KB Output is correct
8 Correct 8 ms 604 KB Output is correct
9 Correct 7 ms 600 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 6 ms 604 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 5 ms 604 KB Output is correct
15 Correct 5 ms 604 KB Output is correct
16 Correct 5 ms 604 KB Output is correct
17 Correct 5 ms 604 KB Output is correct
18 Correct 5 ms 604 KB Output is correct
19 Correct 5 ms 604 KB Output is correct
20 Correct 5 ms 604 KB Output is correct
21 Correct 561 ms 16428 KB Output is correct
22 Correct 566 ms 16344 KB Output is correct
23 Correct 564 ms 16092 KB Output is correct
24 Correct 550 ms 15960 KB Output is correct
25 Correct 518 ms 16048 KB Output is correct
26 Correct 532 ms 16176 KB Output is correct
27 Correct 529 ms 16076 KB Output is correct
28 Correct 518 ms 16208 KB Output is correct
29 Correct 530 ms 16192 KB Output is correct
30 Correct 532 ms 16128 KB Output is correct
31 Correct 586 ms 16136 KB Output is correct
32 Correct 571 ms 16208 KB Output is correct
33 Correct 534 ms 15892 KB Output is correct
34 Correct 560 ms 15908 KB Output is correct
35 Correct 533 ms 15944 KB Output is correct
36 Correct 575 ms 16904 KB Output is correct
37 Correct 564 ms 16912 KB Output is correct
38 Correct 605 ms 17060 KB Output is correct
39 Correct 530 ms 16960 KB Output is correct
40 Correct 545 ms 16840 KB Output is correct
41 Correct 545 ms 16704 KB Output is correct
42 Correct 557 ms 17004 KB Output is correct
43 Correct 603 ms 16936 KB Output is correct
44 Correct 569 ms 16932 KB Output is correct
45 Correct 531 ms 16928 KB Output is correct
46 Correct 581 ms 16936 KB Output is correct
47 Correct 529 ms 17020 KB Output is correct
48 Correct 544 ms 16700 KB Output is correct
49 Correct 571 ms 16800 KB Output is correct
50 Correct 543 ms 16576 KB Output is correct