답안 #745240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745240 2023-05-19T15:27:41 Z MrBrionix Candies (JOI18_candies) C++17
컴파일 오류
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;
 
 
const int MAXN = 200'005;
const long long INF = 1'000'000'000'015;
 
template <class Select>
vector<int> smawk(const int row_size, const int col_size,
  const Select &sel){
  using vi = vector<int>;
  const function<vi(const vi&,const vi&)> solve =
    [&](const vi &row, const vi &col) -> vi{
    const int n = row.size();
    if (n == 0) return {};
    vi c2, r2;
    for(const int i : col){
      while(!c2.empty()&&sel(row[c2.size()-1],c2.back(),i))
        c2.pop_back();
      if (c2.size() < n) c2.push_back(i);
    }
    for(int i = 1; i < n; i += 2) r2.push_back(row[i]);
    const vi a2 = solve(r2, c2); vi ans(n);
    for(int i = 0; i != a2.size(); i += 1) ans[i*2+1]=a2[i];
    int j = 0;
    for(int i = 0; i < n; i += 2){
      ans[i] = c2[j];
      const int end = i + 1 == n ? c2.back() : ans[i + 1];
      while (c2[j] != end){
        j += 1;
        if(sel(row[i], ans[i], c2[j])) ans[i] = c2[j];
      }
    }
    return ans;
  };
  vi row(row_size);iota(row.begin(), row.end(), 0);
  vi col(col_size);iota(col.begin(), col.end(), 0);
  return solve(row, col);
}
template <class T> // a qualsiasi, b convesso
vector<T> conv(const vector<T> &a, const vector<T> &b){
  const int n = a.size(); const int m = b.size();
  const auto get = [&](const int i, const int j){
    return a[j] + b[i - j];
  };
  const auto sel=[&](const int i,const int j,const int k){
    if (i < k) return false;
    if (i - j >= m) return true;
    return get(i, j) <= get(i, k);
  };
  const vector<int> amax = smawk(n + m - 1, n, sel);
  vector<T> c(n + m - 1);
  for (int i = 0; i != n + m - 1; i += 1)
    c[i] = get(i, amax[i]);
  return c;
} //$\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 = concave_max_plus_convolution(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;
  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

candies.cpp: In lambda function:
candies.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i != a2.size(); i += 1) ans[i*2+1]=a2[i];
      |                    ~~^~~~~~~~~~~~
candies.cpp: In function 'dp f(int, int)':
candies.cpp:103:20: error: 'concave_max_plus_convolution' was not declared in this scope
  103 |         auto tmp = concave_max_plus_convolution(le.mat[i][k],ri.mat[k][j]);
      |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~