Submission #745165

#	Time	Username	Problem	Language	Result	Execution time	Memory
745165		MrBrionix	Candies (JOI18_candies)	C++17	8 / 100	630 ms	38872 KiB

candies

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200'005;
const long long INF = 1'000'000'000'000'015;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;


template<class F,class D=ll>
vi smawk(F f,int n,int m){
  vi ans(n,-1);
  auto rec=[&](auto self,int*const rs,int x,int*const cs,int y)->void{
    const int t=8;
    if(x<=t||y<=t){
      rep(i,x){
        int r=rs[i];
        D mx;
        rep(j,y){
          int c=cs[j];
          D w=f(r,c);
          if(ans[r]==-1||w>mx){
            ans[r]=c;
            mx=w;
          }
        }
      }
      return;
    }
    if(x<y){
      int s=0;
      rep(i,y){
        int c=cs[i];
        while(s&&f(rs[s-1],cs[s-1])<f(rs[s-1],c))
          s--;
        if(s<x)
          cs[s++]=c;
      }
      y=s;
    }
    auto a=rs+x,b=cs+y;
    int z=0;
    for(int i=1;i<x;i+=2)
      a[z++]=rs[i];
    rep(i,y)
    b[i]=cs[i];
    self(self,a,z,b,y);
    int k=0;
    for(int i=0;i<x;i+=2){
      int to=i+1<x?ans[rs[i+1]]:cs[y-1];
      D mx;
      while(1){
        D w=f(rs[i],cs[k]);
        if(ans[rs[i]]==-1||w>mx){
          ans[rs[i]]=cs[k];
          mx=w;
        }
        if(cs[k]==to)break;
        k++;
      }
    }
  };
  int*rs=new int[n*2];
  rep(i,n)rs[i]=i;
  int*cs=new int[max(m,n*2)];
  rep(i,m)cs[i]=i;
  rec(rec,rs,n,cs,m);
  delete[] rs;
  delete[] cs;
  return ans;
}
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_MIN;
    if(j<0 || j>=n){exit(0);}
    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<int> best = smawk(function, n + m - 1, n);
  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;
  
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  
  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 (stderr)

candies.cpp: In instantiation of 'std::vector<_Tp> MaxConvolutionWithConvexShape(std::vector<_Tp>, const std::vector<_Tp>&) [with T = long long int]':
candies.cpp:170:75:   required from here
candies.cpp:113:8: warning: variable 'comparator' set but not used [-Wunused-but-set-variable]
  113 |   auto comparator = [&](int i, int j, int k) {
      |        ^~~~~~~~~~
candies.cpp: In lambda function:
candies.cpp:83:26: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |         if(ans[rs[i]]==-1||w>mx){
candies.cpp:80:9: note: 'mx' was declared here
   80 |       D mx;
      |         ^~
candies.cpp:51:24: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |           if(ans[r]==-1||w>mx){
candies.cpp:47:11: note: 'mx' was declared here
   47 |         D mx;
      |           ^~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92