oj.uz

Submission #745216

# Submission time Handle Problem Language Result Execution time Memory
745216 2023-05-19T14:59:55 Z MrBrionix Candies (JOI18_candies) C++17
100 / 100
 2790 ms 22836 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 19 ms 468 KB Output is correct
2 Correct 19 ms 468 KB Output is correct
3 Correct 20 ms 484 KB Output is correct
4 Correct 19 ms 468 KB Output is correct
5 Correct 18 ms 468 KB Output is correct
6 Correct 26 ms 512 KB Output is correct
7 Correct 18 ms 448 KB Output is correct
8 Correct 19 ms 472 KB Output is correct
9 Correct 17 ms 468 KB Output is correct
10 Correct 18 ms 532 KB Output is correct
11 Correct 20 ms 468 KB Output is correct
12 Correct 20 ms 552 KB Output is correct
13 Correct 19 ms 480 KB Output is correct
14 Correct 23 ms 540 KB Output is correct
15 Correct 21 ms 564 KB Output is correct
16 Correct 19 ms 524 KB Output is correct
17 Correct 20 ms 516 KB Output is correct
18 Correct 21 ms 468 KB Output is correct
19 Correct 19 ms 468 KB Output is correct
20 Correct 19 ms 468 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 468 KB Output is correct
2 Correct 19 ms 468 KB Output is correct
3 Correct 20 ms 484 KB Output is correct
4 Correct 19 ms 468 KB Output is correct
5 Correct 18 ms 468 KB Output is correct
6 Correct 26 ms 512 KB Output is correct
7 Correct 18 ms 448 KB Output is correct
8 Correct 19 ms 472 KB Output is correct
9 Correct 17 ms 468 KB Output is correct
10 Correct 18 ms 532 KB Output is correct
11 Correct 20 ms 468 KB Output is correct
12 Correct 20 ms 552 KB Output is correct
13 Correct 19 ms 480 KB Output is correct
14 Correct 23 ms 540 KB Output is correct
15 Correct 21 ms 564 KB Output is correct
16 Correct 19 ms 524 KB Output is correct
17 Correct 20 ms 516 KB Output is correct
18 Correct 21 ms 468 KB Output is correct
19 Correct 19 ms 468 KB Output is correct
20 Correct 19 ms 468 KB Output is correct
21 Correct 2271 ms 22744 KB Output is correct
22 Correct 2790 ms 20792 KB Output is correct
23 Correct 2416 ms 21004 KB Output is correct
24 Correct 2168 ms 22692 KB Output is correct
25 Correct 2093 ms 21404 KB Output is correct
26 Correct 2104 ms 20888 KB Output is correct
27 Correct 2203 ms 20872 KB Output is correct
28 Correct 2359 ms 21000 KB Output is correct
29 Correct 2301 ms 22824 KB Output is correct
30 Correct 2348 ms 21212 KB Output is correct
31 Correct 2293 ms 22836 KB Output is correct
32 Correct 2407 ms 22784 KB Output is correct
33 Correct 2326 ms 22064 KB Output is correct
34 Correct 2117 ms 22468 KB Output is correct
35 Correct 2153 ms 20984 KB Output is correct
36 Correct 2220 ms 21080 KB Output is correct
37 Correct 2166 ms 21484 KB Output is correct
38 Correct 2186 ms 21288 KB Output is correct
39 Correct 1995 ms 21632 KB Output is correct
40 Correct 1986 ms 22824 KB Output is correct
41 Correct 1973 ms 20916 KB Output is correct
42 Correct 2143 ms 20988 KB Output is correct
43 Correct 2103 ms 21644 KB Output is correct
44 Correct 2119 ms 21028 KB Output is correct
45 Correct 2127 ms 22780 KB Output is correct
46 Correct 2101 ms 21208 KB Output is correct
47 Correct 2111 ms 21112 KB Output is correct
48 Correct 2133 ms 21104 KB Output is correct
49 Correct 2129 ms 22556 KB Output is correct
50 Correct 2148 ms 20920 KB Output is correct