oj.uz

Submission #946506

# Submission time Handle Problem Language Result Execution time Memory
946506 2024-03-14T17:27:57 Z Sokol080808 Candies (JOI18_candies) C++14
100 / 100
 1037 ms 16160 KB 
#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <malloc.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& p) {in >> p.first >> p.second; return in;}
template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2>& p) {out << p.first << ' ' << p.second; return out;}
template<typename T> istream& operator>>(istream& in, vector<T>& v) {for (auto& x : v) in >> x; return in;}
template<typename T> ostream& operator<<(ostream& out, vector<T>& v) {for (auto& x : v) out << x << ' '; return out;}
template<typename T> ostream& operator<<(ostream& out, set<T>& v) {for (auto& x : v) out << x << ' '; return out;}
template<typename T> ostream& operator<<(ostream& out, multiset<T>& v) {for (auto& x : v) out << x << ' '; return out;}

const int MAX_INT = 2147483647;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<ll> getmax(const vector<ll>& a, const vector<ll>& b) {
    int n = max(a.size(), b.size());
    vector<ll> res(n, -1e18);
    for (int i = 0; i < n; i++) {
        if (i < a.size()) res[i] = max(res[i], a[i]);
        if (i < b.size()) res[i] = max(res[i], b[i]);
    }
    return res;
}

vector<ll> conv(const vector<ll>& a, const vector<ll>& b) {
    vector<ll> d;
    for (int i = 0; i + 1 < a.size(); i++) d.push_back(a[i + 1] - a[i]);
    for (int i = 0; i + 1 < b.size(); i++) d.push_back(b[i + 1] - b[i]);
    sort(rall(d));
    vector<ll> res(d.size() + 1);
    res[0] = a[0] + b[0];
    for (int i = 0; i < d.size(); i++) res[i + 1] = res[i] + d[i];
    return res;
}

vector<int> a;

using info = array<array<vector<ll>, 2>, 2>;

info solve(int l, int r) {
    if (l + 1 == r) {
        info res;
        res[0][0] = {0};
        res[0][1] = {-(ll)1e18};
        res[1][0] = {-(ll)1e18};
        res[1][1] = {0, a[l]};
        return res;
    }

    int m = (l + r) / 2;
    info left = solve(l, m);
    info right = solve(m, r);

    info res;
    for (int a = 0; a <= 1; a++) {
        for (int b = 0; b <= 1; b++) {
            for (int c = 0; c <= 1; c++) {
                for (int d = 0; d <= 1; d++) {
                    if (b == 1 && c == 1) continue;
                    res[a][d] = getmax(res[a][d], conv(left[a][b], right[c][d]));
                }
            }
        }
    }

    return res;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    a.resize(n);
    sort(all(a));
    for (int i = 0; i < n; i++) cin >> a[i];

    info var = solve(0, n);
    vector<ll> res;
    for (int a = 0; a <= 1; a++) {
        for (int b = 0; b <= 1; b++) {
            res = getmax(res, var[a][b]);
        }
    }

    for (int i = 1; i <= (n + 1) / 2; i++) cout << res[i] << '\n';

    return 0;
}

Compilation message

candies.cpp: In function 'std::vector<long long int> getmax(const std::vector<long long int>&, const std::vector<long long int>&)':
candies.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if (i < a.size()) res[i] = max(res[i], a[i]);
      |             ~~^~~~~~~~~~
candies.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (i < b.size()) res[i] = max(res[i], b[i]);
      |             ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<long long int> conv(const std::vector<long long int>&, const std::vector<long long int>&)':
candies.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i + 1 < a.size(); i++) d.push_back(a[i + 1] - a[i]);
      |                     ~~~~~~^~~~~~~~~~
candies.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i + 1 < b.size(); i++) d.push_back(b[i + 1] - b[i]);
      |                     ~~~~~~^~~~~~~~~~
candies.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < d.size(); i++) res[i + 1] = res[i] + d[i];
      |                     ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 604 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 5 ms 856 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 6 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 500 KB Output is correct
16 Correct 6 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 6 ms 604 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 5 ms 856 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 6 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 500 KB Output is correct
16 Correct 6 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 1028 ms 14452 KB Output is correct
22 Correct 1034 ms 14440 KB Output is correct
23 Correct 1016 ms 14720 KB Output is correct
24 Correct 668 ms 14676 KB Output is correct
25 Correct 649 ms 14632 KB Output is correct
26 Correct 638 ms 14672 KB Output is correct
27 Correct 649 ms 14716 KB Output is correct
28 Correct 596 ms 14720 KB Output is correct
29 Correct 612 ms 14512 KB Output is correct
30 Correct 626 ms 14480 KB Output is correct
31 Correct 673 ms 14796 KB Output is correct
32 Correct 616 ms 14476 KB Output is correct
33 Correct 752 ms 14612 KB Output is correct
34 Correct 714 ms 14736 KB Output is correct
35 Correct 716 ms 14752 KB Output is correct
36 Correct 1016 ms 15952 KB Output is correct
37 Correct 1034 ms 16148 KB Output is correct
38 Correct 1037 ms 15956 KB Output is correct
39 Correct 658 ms 16160 KB Output is correct
40 Correct 656 ms 15840 KB Output is correct
41 Correct 660 ms 15956 KB Output is correct
42 Correct 625 ms 15936 KB Output is correct
43 Correct 626 ms 15860 KB Output is correct
44 Correct 623 ms 15744 KB Output is correct
45 Correct 621 ms 15908 KB Output is correct
46 Correct 628 ms 15916 KB Output is correct
47 Correct 620 ms 15904 KB Output is correct
48 Correct 720 ms 16136 KB Output is correct
49 Correct 719 ms 15928 KB Output is correct
50 Correct 781 ms 15776 KB Output is correct