oj.uz

Submission #745219

# Submission time Handle Problem Language Result Execution time Memory
745219 2023-05-19T15:04:16 Z MrBrionix Candies (JOI18_candies) C++17
100 / 100
 2912 ms 23156 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 &select){
  using vec_zu = vector<int>;
  const function<vec_zu(const vec_zu&, const vec_zu&)> solve=
  [&](const vec_zu &row, const vec_zu &col) -> vec_zu{
    const int n = row.size();
    if (n == 0) return {};
    vec_zu c2;
    for(const int 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(int i = 1; i < n; i += 2) r2.push_back(row[i]);
    const vec_zu a2 = solve(r2, c2);
    vec_zu 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(select(row[i], ans[i], c2[j])) ans[i] = c2[j];
      }
    }
    return ans;
  };
  vec_zu row(row_size);iota(row.begin(), row.end(), 0);
  vec_zu col(col_size);iota(col.begin(), col.end(), 0);
  return solve(row, col);
}
template <class T>
vector<T> concave_max_plus_convolution(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 select=[&](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, select);
  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:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i != a2.size(); i += 1) ans[i*2+1]=a2[i];
      |                    ~~^~~~~~~~~~~~
candies.cpp: In instantiation of 'std::vector<int> smawk(int, int, const Select&) [with Select = concave_max_plus_convolution<long long int>::<lambda(int, int, int)>]':
candies.cpp:54:33:   required from 'std::vector<_Tp> concave_max_plus_convolution(const std::vector<_Tp>&, const std::vector<_Tp>&) [with T = long long int]'
candies.cpp:106:74:   required from here
candies.cpp:20:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   20 |       if (c2.size() < n) c2.push_back(i);
      |           ~~~~~~~~~~^~~
candies.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i != a2.size(); i += 1) ans[i*2+1]=a2[i];
      |                    ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Output is correct
2 Correct 18 ms 596 KB Output is correct
3 Correct 18 ms 596 KB Output is correct
4 Correct 18 ms 536 KB Output is correct
5 Correct 18 ms 468 KB Output is correct
6 Correct 18 ms 548 KB Output is correct
7 Correct 17 ms 540 KB Output is correct
8 Correct 18 ms 528 KB Output is correct
9 Correct 18 ms 560 KB Output is correct
10 Correct 17 ms 468 KB Output is correct
11 Correct 19 ms 468 KB Output is correct
12 Correct 18 ms 552 KB Output is correct
13 Correct 20 ms 560 KB Output is correct
14 Correct 20 ms 596 KB Output is correct
15 Correct 19 ms 552 KB Output is correct
16 Correct 19 ms 532 KB Output is correct
17 Correct 22 ms 532 KB Output is correct
18 Correct 19 ms 548 KB Output is correct
19 Correct 20 ms 468 KB Output is correct
20 Correct 17 ms 532 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Output is correct
2 Correct 18 ms 596 KB Output is correct
3 Correct 18 ms 596 KB Output is correct
4 Correct 18 ms 536 KB Output is correct
5 Correct 18 ms 468 KB Output is correct
6 Correct 18 ms 548 KB Output is correct
7 Correct 17 ms 540 KB Output is correct
8 Correct 18 ms 528 KB Output is correct
9 Correct 18 ms 560 KB Output is correct
10 Correct 17 ms 468 KB Output is correct
11 Correct 19 ms 468 KB Output is correct
12 Correct 18 ms 552 KB Output is correct
13 Correct 20 ms 560 KB Output is correct
14 Correct 20 ms 596 KB Output is correct
15 Correct 19 ms 552 KB Output is correct
16 Correct 19 ms 532 KB Output is correct
17 Correct 22 ms 532 KB Output is correct
18 Correct 19 ms 548 KB Output is correct
19 Correct 20 ms 468 KB Output is correct
20 Correct 17 ms 532 KB Output is correct
21 Correct 2424 ms 22572 KB Output is correct
22 Correct 2418 ms 22604 KB Output is correct
23 Correct 2415 ms 21028 KB Output is correct
24 Correct 2017 ms 22780 KB Output is correct
25 Correct 2167 ms 21312 KB Output is correct
26 Correct 2148 ms 20892 KB Output is correct
27 Correct 2241 ms 21012 KB Output is correct
28 Correct 2247 ms 21104 KB Output is correct
29 Correct 2387 ms 22776 KB Output is correct
30 Correct 2244 ms 21124 KB Output is correct
31 Correct 2220 ms 22836 KB Output is correct
32 Correct 2231 ms 21720 KB Output is correct
33 Correct 2557 ms 21876 KB Output is correct
34 Correct 2283 ms 22296 KB Output is correct
35 Correct 2912 ms 20960 KB Output is correct
36 Correct 2152 ms 21600 KB Output is correct
37 Correct 2147 ms 20832 KB Output is correct
38 Correct 2140 ms 21332 KB Output is correct
39 Correct 1962 ms 21408 KB Output is correct
40 Correct 1912 ms 22984 KB Output is correct
41 Correct 1945 ms 21068 KB Output is correct
42 Correct 2070 ms 20916 KB Output is correct
43 Correct 2110 ms 21656 KB Output is correct
44 Correct 2048 ms 21168 KB Output is correct
45 Correct 2081 ms 23156 KB Output is correct
46 Correct 2050 ms 21436 KB Output is correct
47 Correct 2049 ms 21152 KB Output is correct
48 Correct 2083 ms 21136 KB Output is correct
49 Correct 2099 ms 23024 KB Output is correct
50 Correct 2061 ms 20920 KB Output is correct