Submission #745143

#	Time	Username	Problem	Language	Result	Execution time	Memory
745143		MrBrionix	Candies (JOI18_candies)	C++17	0 / 100	14 ms	596 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;

template<class F>
vector<int> smawck(F f, const vector<int> &rows,
  const vector<int> &cols) {
  vector<int> ans(rows.size(), -1);
  if((int) max(rows.size(), cols.size()) <= 2) {
    for(int i = 0; i < (int) rows.size(); i++) {
      for(auto j : cols) {
        if(ans[i] == -1 || f(rows[i], ans[i], j))
          ans[i] = j;
      }
    }
  } else if(rows.size() < cols.size()) { // reduce
    vector<int> st;
    for(int j : cols) {
      while(1) {
        if(st.empty()) {
          st.push_back(j);
          break;
        }else if(f(rows[(int)st.size()-1], st.back(), j)){
          st.pop_back();
        } else if(st.size() < rows.size()) {
          st.push_back(j);
          break;
        } else {
          break;
        }
      }
    }
    ans = smawck(f, rows, st);
  } else {
    vector<int> newRows;
    for(int i = 1; i < (int) rows.size(); i += 2) {
      newRows.push_back(rows[i]);
    }
    auto otherAns = smawck(f, newRows, cols);
    for(int i = 0; i < (int) newRows.size(); i++) {
      ans[2*i+1] = otherAns[i];
    }
    for(int i = 0, l = 0, r = 0; i < (int)rows.size();i+=2){
      while(l && cols[l-1] >= ans[i-1]) l--;
      if(i+1 == (int) rows.size()) r = (int) cols.size();
      while(r < (int) cols.size() && r <= ans[i+1]) r++;
      ans[i] = cols[l++];
      for(; l < r; l++) {
        if(f(rows[i], ans[i], cols[l]))
          ans[i] = cols[l];
      }
      l--;
    }
  }
  return ans;
}
/* F(i, j, k) checks if M[i][j] $\leq$ M[i][k]
 * another interpretations is: F(i, j, k) checks if
 * M[i][k] is at least as good as M[i][j] (higher == better)
 * when comparing 2 columns as vectors for j < k, 
 *column j can start better than column k. as soon as column
 * k is at least as good, it's always at least as good */
template<class F>
vector<int> smawck(F f, int n, int m) {
  vector<int> rows(n), cols(m);
  for(int i = 0; i < n; i++) rows[i] = i;
  for(int i = 0; i < m; i++) cols[i] = i;
  return smawck(f, rows, cols);
}
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) {
    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 = smawck(comparator, 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+1)/2),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+1)/2;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";
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int t=1;
  //cin>>t;
  for(int i=1;i<=t;i++)solve();
  
  return 0;
}

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