oj.uz

답안 #877123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877123 2023-11-22T22:37:17 Z SorahISA Candies (JOI18_candies) C++17
100 / 100
 607 ms 27360 KB 
#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

struct State {
    
    vector<int> v;
    
    State () { v = {0}; }
    State (int base) { v = {0, base}; }
    State (int type, const vector<int> &arr) {
        if (type == 0) {
            /// value ///
            v = arr;
        }
        if (type == 1) {
            /// diff ///
            v.resize(SZ(arr) + 1);
            v[0] = 0;
            for (int i = 0; i < SZ(arr); ++i) v[i+1] = v[i] + arr[i];
        }
    }
    
    int& operator [] (int x)       { return v[x]; }
    int  operator [] (int x) const { return v[x]; }
    
    State operator + (const State &rhs) {
        int sz_l = SZ(v), sz_r = SZ(rhs.v);
        vector<int> slope_l, slope_r;
        for (int i = 1; i < sz_l; ++i) slope_l.eb(v[i] - v[i-1]);
        for (int i = 1; i < sz_r; ++i) slope_r.eb(rhs[i] - rhs[i-1]);
        vector<int> merged_slope;
        auto it_l = cbegin(slope_l), it_r = cbegin(slope_r);
        while (it_l != cend(slope_l) and it_r != cend(slope_r)) {
            if (*it_l >= *it_r) merged_slope.eb(*it_l), ++it_l;
            else                merged_slope.eb(*it_r), ++it_r;
        }
        while (it_l != cend(slope_l)) merged_slope.eb(*it_l), ++it_l;
        while (it_r != cend(slope_r)) merged_slope.eb(*it_r), ++it_r;
        return State(1, merged_slope);
    }
    
    friend State max(const State &lhs, const State &rhs) {
        int sz_l = SZ(lhs.v), sz_r = SZ(rhs.v);
        vector<int> res(max(sz_l, sz_r), 0);
        for (int i = 0; i < sz_l; ++i) chmax(res[i], lhs[i]);
        for (int i = 0; i < sz_r; ++i) chmax(res[i], rhs[i]);
        return State(0, res);
    }
    
    friend State max(const State &s1, const State &s2, const State &s3) {
        return max(s1, max(s2, s3));
    }
    
};

void solve() {
    int N; cin >> N;
    
    vector<int> A(N);
    for (int &x : A) cin >> x;
    
    function<array<State, 4>(int, int)> recur = [&](int L, int R) -> array<State, 4> {
        if (L == R) { return array<State, 4>{State(), State(), State(), State(A[L])}; }
        
        int M = (L + R) >> 1;
        auto dpL = recur(L, M), dpR = recur(M+1, R);
        
        return array<State, 4>{
            max(dpL[0] + dpR[0], dpL[0] + dpR[2], dpL[1] + dpR[0]),
            max(dpL[0] + dpR[1], dpL[0] + dpR[3], dpL[1] + dpR[1]),
            max(dpL[2] + dpR[0], dpL[2] + dpR[2], dpL[3] + dpR[0]),
            max(dpL[2] + dpR[1], dpL[2] + dpR[3], dpL[3] + dpR[1])
        };
    };
    
    auto dp = recur(0, N-1);
    
    for (int i = 1; i <= (N+1)/2; ++i) {
        int ans = 0;
        for (int j : {0, 1, 2, 3}) {
            if (i < SZ(dp[j].v)) chmax(ans, dp[j][i]);
        }
        print(ans);
    }
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case #" << _ << ": ";
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
};

template <typename T> struct Vec<1, T> : vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
    return [f = std::forward<F>(f)](auto&&... args) {
        return f(f, std::forward<decltype(args)>(args)...);
    };
}

#ifdef local
#define fastIO() void()
#define debug(...) \
    _color.emplace_back("\u001b[31m"), \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), _color.pop_back(), \
    fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
    fprintf(stdout, "%s", "\u001b[36m"), \
    _P(__VA_ARGS__), \
    fprintf(stdout, "%s", "\u001b[0m")

deque<string> _color{"\u001b[0m"};

template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) {begin(_t);};

template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);

inline void _do() {cerr << "\n";};
template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";}
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif

inline void _P() {cout << "\n";};
template <typename T> inline void _P(T &&_t) {cout << _t << "\n";}
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) {cout << _t << " ", _P(_u...);}

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

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % ((uint64_t)R - L + 1) + L);
}

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

/// below are Fast I/O and _print_err templates ///

/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#include <unistd.h>

const int S = 65536;

int OP = 0;
char OB[S];

inline char RC() {
    static char buf[S], *p = buf, *q = buf;
    return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}

inline int RI() {
    static char c;
    int a;
    while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
    if (c == '-') {
        a = 0;
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
    }
    else {
        a = c ^ '0';
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
    }
    return a;
}

inline void WI(int n, char c = '\n') {
    static char buf[20], p;
    if (n == 0) OB[OP++] = '0';
    p = 0;
    if (n < 0) {
        OB[OP++] = '-';
        while (n) buf[p++] = '0' - (n % 10), n /= 10;
    }
    else {
        while (n) buf[p++] = '0' + (n % 10), n /= 10;
    }
    for (--p; p >= 0; --p) OB[OP++] = buf[p];
    OB[OP++] = c;
    if (OP > S-20) write(1, OB, OP), OP = 0;
}

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/

#ifdef local

template <typename T> inline void _print_err(T &&_t) {cerr << _t;}

template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "[";
    for (bool _first = true; auto &_x : _t) {
        if (!_first) cerr << ", ";
        _print_err(_x), _first = false;
    }
    cerr << "]" << (_color.pop_back(), _color.back());
}

template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "(";
    _print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
    cerr << ")" << (_color.pop_back(), _color.back());
    return os;
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

#endif

#endif

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 5 ms 600 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 648 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 728 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 8 ms 604 KB Output is correct
16 Correct 5 ms 544 KB Output is correct
17 Correct 5 ms 600 KB Output is correct
18 Correct 5 ms 604 KB Output is correct
19 Correct 5 ms 732 KB Output is correct
20 Correct 5 ms 600 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 5 ms 600 KB Output is correct
8 Correct 5 ms 604 KB Output is correct
9 Correct 5 ms 648 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 728 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 8 ms 604 KB Output is correct
16 Correct 5 ms 544 KB Output is correct
17 Correct 5 ms 600 KB Output is correct
18 Correct 5 ms 604 KB Output is correct
19 Correct 5 ms 732 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 575 ms 25236 KB Output is correct
22 Correct 562 ms 25188 KB Output is correct
23 Correct 589 ms 25220 KB Output is correct
24 Correct 525 ms 25208 KB Output is correct
25 Correct 529 ms 25096 KB Output is correct
26 Correct 514 ms 25248 KB Output is correct
27 Correct 540 ms 25560 KB Output is correct
28 Correct 530 ms 25224 KB Output is correct
29 Correct 549 ms 25272 KB Output is correct
30 Correct 594 ms 25244 KB Output is correct
31 Correct 538 ms 25460 KB Output is correct
32 Correct 528 ms 25220 KB Output is correct
33 Correct 536 ms 25116 KB Output is correct
34 Correct 535 ms 25192 KB Output is correct
35 Correct 547 ms 25036 KB Output is correct
36 Correct 565 ms 27360 KB Output is correct
37 Correct 566 ms 27256 KB Output is correct
38 Correct 563 ms 27248 KB Output is correct
39 Correct 522 ms 27308 KB Output is correct
40 Correct 546 ms 27008 KB Output is correct
41 Correct 524 ms 27076 KB Output is correct
42 Correct 532 ms 27256 KB Output is correct
43 Correct 539 ms 27200 KB Output is correct
44 Correct 545 ms 27244 KB Output is correct
45 Correct 526 ms 27256 KB Output is correct
46 Correct 549 ms 27096 KB Output is correct
47 Correct 541 ms 27268 KB Output is correct
48 Correct 607 ms 27256 KB Output is correct
49 Correct 545 ms 26924 KB Output is correct
50 Correct 553 ms 27000 KB Output is correct