#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
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
