#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
const int MAXN = 200'005;
const long long INF = 1'000'000'000'000'015;
template <class Select>
std::vector<usize> smawk(const usize row_size, const usize col_size,
const Select &select) {
using vec_zu = std::vector<usize>;
const std::function<vec_zu(const vec_zu &, const vec_zu &)> solve =
[&](const vec_zu &row, const vec_zu &col) -> vec_zu {
const usize n = row.size();
if (n == 0)
return {};
vec_zu c2;
for (const usize i : col) {
while (!c2.empty() && select(row[c2.size() - 1], c2.back(), i))
c2.pop_back();
if (c2.size() < n)
c2.push_back(i);
}
vec_zu r2;
for (usize i = 1; i < n; i += 2)
r2.push_back(row[i]);
const vec_zu a2 = solve(r2, c2);
vec_zu ans(n);
for (usize i = 0; i != a2.size(); i += 1)
ans[i * 2 + 1] = a2[i];
usize j = 0;
for (usize i = 0; i < n; i += 2) {
ans[i] = c2[j];
const usize end = i + 1 == n ? c2.back() : ans[i + 1];
while (c2[j] != end) {
j += 1;
if (select(row[i], ans[i], c2[j]))
ans[i] = c2[j];
}
}
return ans;
};
vec_zu row(row_size);
std::iota(row.begin(), row.end(), 0);
vec_zu col(col_size);
std::iota(col.begin(), col.end(), 0);
return solve(row, col);
}
template<class T>
vector<T> MaxConvolutionWithConvexShape(vector<T> anyShape,
const vector<T> &convexShape) {
if((int) convexShape.size() <= 1) return anyShape;
if(anyShape.empty()) anyShape.push_back(0);
int n = (int)anyShape.size(), m = (int)convexShape.size();
auto function = [&](int i, int j) {
//if(i-j<0 || i-j>=m) return -LLONG_MAX/3ll;
//if(j<0 || j>=n) return -LLONG_MAX/3ll;
return anyShape[j] + convexShape[i-j];
};
auto comparator = [&](int i, int j, int k) {
if(i < k) return false;
if(i - j >= m) return true;
return function(i, j) <= function(i, k);
};
const vector<unsigned long long> best = smawk(n + m - 1 , n, comparator);
vector<T> ans(n + m - 1);
for(int i = 0; i < n + m - 1; i++)
ans[i] = function(i, best[i]);
return ans;
} //$\mathit{ans}_i=\max_{j+k=i}(A_j+B_k)$
int n,r;
long long a[MAXN];
struct dp{
vector<long long> mat[2][2];
dp(){}
dp(int n){
mat[0][0]=vector<long long>(n+1,LLONG_MIN);
mat[0][1]=vector<long long>(n+1,LLONG_MIN);
mat[1][0]=vector<long long>(n+1,LLONG_MIN);
mat[1][1]=vector<long long>(n+1,LLONG_MIN);
}
dp(vector<long long> a,vector<long long>b,vector<long long>c,vector<long long>d){
mat[0][0]=a;
mat[0][1]=b;
mat[1][0]=c;
mat[1][1]=d;
}
};
dp f(int l,int r){
if(l+1==r){
return dp({0,-INF},{-INF,-INF},{-INF,-INF},{-INF,a[l]});
}
if(l+2==r){
return dp({0,-INF,-2ll*INF-1ll},{-INF,a[l+1],-INF},{-INF,a[l],-INF},{-3ll*INF-3ll,-2*INF-1ll,-INF});
}
dp res(r-l),le,ri;
if((r-l)%2 == 1){
le = f(l,(l+r)/2+1);
ri = f((l+r)/2,r);
}else{
le = f(l,(l+r)/2);
ri = f((l+r)/2-1,r);
}
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
auto tmp = MaxConvolutionWithConvexShape(le.mat[i][k],ri.mat[k][j]);
for(int ll=0;ll<=r-l;ll++){
res.mat[i][j][ll] = max(res.mat[i][j][ll],tmp[ll+k]-k*a[(r-l)%2 == 1 ? (l+r)/2 : (l+r)/2-1]);
}
}
}
}
return res;
}
void solve(){
cin>>n;
//cin>>r;
//n = 90'000;
for(int i=0;i<n;i++){
cin>>a[i];
//a[i]=10;
}
auto tmp = f(0,n);
for(int i=1;i<=(n+1)/2;i++)
cout<<max({tmp.mat[0][0][i],tmp.mat[0][1][i],tmp.mat[1][0][i],tmp.mat[1][1][i]})<<"\n";
}
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
Compilation message
candies.cpp: In instantiation of 'std::vector<_Tp> MaxConvolutionWithConvexShape(std::vector<_Tp>, const std::vector<_Tp>&) [with T = long long int]':
candies.cpp:127:75: required from here
candies.cpp:75:48: error: conversion from 'vector<long unsigned int>' to non-scalar type 'vector<long long unsigned int>' requested
75 | const vector<unsigned long long> best = smawk(n + m - 1 , n, comparator);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
