oj.uz

Submission #745204

# Submission time Handle Problem Language Result Execution time Memory
745204 2023-05-19T14:45:14 Z MrBrionix Candies (JOI18_candies) C++17
100 / 100
 2153 ms 28092 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;


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

using i32 = long long;
using i64 = long long;
using u32 = long long;
using u64 = long long;
using isize = long long;
using usize = long long;

template <class Select>
std::vector<usize> smawk(const usize row_size, const usize col_size,
  const Select &select) {
  using vec_zu = std::vector<usize>;
  
  const std::function<vec_zu(const vec_zu &, const vec_zu &)> solve =
  [&](const vec_zu &row, const vec_zu &col) -> vec_zu {
    const usize n = row.size();
    if (n == 0)
      return {};
    vec_zu c2;
    for (const usize 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 (usize i = 1; i < n; i += 2)
      r2.push_back(row[i]);
    const vec_zu a2 = solve(r2, c2);
    vec_zu ans(n);
    for (usize i = 0; i != a2.size(); i += 1)
      ans[i * 2 + 1] = a2[i];
    usize j = 0;
    for (usize i = 0; i < n; i += 2) {
      ans[i] = c2[j];
      const usize 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);
  std::iota(row.begin(), row.end(), 0);
  vec_zu col(col_size);
  std::iota(col.begin(), col.end(), 0);
  return solve(row, col);
}

template <class T>
std::vector<T> concave_max_plus_convolution(const std::vector<T> &a,
  const std::vector<T> &b) {
  const usize n = a.size();
  const usize m = b.size();
  const auto get = [&](const usize i, const usize j) {
    return a[j] + b[i - j];
  };
  const auto select = [&](const usize i, const usize j, const usize k) {
    if (i < k)
      return false;
    if (i - j >= m)
      return true;
    return get(i, j) <= get(i, k);
  };
  const std::vector<usize> amax = smawk(n + m - 1, n, select);
  std::vector<T> c(n + m - 1);
  for (usize 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;
  //cin>>r;
  //n = 90'000;
  for(int i=0;i<n;i++){
    cin>>a[i];
    //a[i]=10;
  }
  
  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:38:25: warning: comparison of integer expressions of different signedness: 'usize' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (usize i = 0; i != a2.size(); i += 1)
      |                       ~~^~~~~~~~~~~~
candies.cpp: In instantiation of 'std::vector<long long int> smawk(usize, usize, const Select&) [with Select = concave_max_plus_convolution<long long int>::<lambda(usize, usize, usize)>; usize = long long int]':
candies.cpp:74:40:   required from 'std::vector<_Tp> concave_max_plus_convolution(const std::vector<_Tp>&, const std::vector<_Tp>&) [with T = long long int]'
candies.cpp:126:74:   required from here
candies.cpp:30:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'const usize' {aka 'const long long int'} [-Wsign-compare]
   30 |       if (c2.size() < n)
      |           ~~~~~~~~~~^~~
candies.cpp:38:25: warning: comparison of integer expressions of different signedness: 'usize' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (usize i = 0; i != a2.size(); i += 1)
      |                       ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 588 KB Output is correct
2 Correct 18 ms 556 KB Output is correct
3 Correct 17 ms 576 KB Output is correct
4 Correct 19 ms 560 KB Output is correct
5 Correct 17 ms 588 KB Output is correct
6 Correct 19 ms 556 KB Output is correct
7 Correct 18 ms 596 KB Output is correct
8 Correct 18 ms 588 KB Output is correct
9 Correct 17 ms 532 KB Output is correct
10 Correct 17 ms 556 KB Output is correct
11 Correct 18 ms 560 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Correct 18 ms 596 KB Output is correct
14 Correct 17 ms 596 KB Output is correct
15 Correct 17 ms 524 KB Output is correct
16 Correct 18 ms 564 KB Output is correct
17 Correct 19 ms 528 KB Output is correct
18 Correct 18 ms 556 KB Output is correct
19 Correct 18 ms 528 KB Output is correct
20 Correct 18 ms 596 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 588 KB Output is correct
2 Correct 18 ms 556 KB Output is correct
3 Correct 17 ms 576 KB Output is correct
4 Correct 19 ms 560 KB Output is correct
5 Correct 17 ms 588 KB Output is correct
6 Correct 19 ms 556 KB Output is correct
7 Correct 18 ms 596 KB Output is correct
8 Correct 18 ms 588 KB Output is correct
9 Correct 17 ms 532 KB Output is correct
10 Correct 17 ms 556 KB Output is correct
11 Correct 18 ms 560 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Correct 18 ms 596 KB Output is correct
14 Correct 17 ms 596 KB Output is correct
15 Correct 17 ms 524 KB Output is correct
16 Correct 18 ms 564 KB Output is correct
17 Correct 19 ms 528 KB Output is correct
18 Correct 18 ms 556 KB Output is correct
19 Correct 18 ms 528 KB Output is correct
20 Correct 18 ms 596 KB Output is correct
21 Correct 2153 ms 25360 KB Output is correct
22 Correct 2121 ms 27064 KB Output is correct
23 Correct 2106 ms 25248 KB Output is correct
24 Correct 1865 ms 26724 KB Output is correct
25 Correct 1890 ms 26716 KB Output is correct
26 Correct 1903 ms 26876 KB Output is correct
27 Correct 1983 ms 27328 KB Output is correct
28 Correct 1990 ms 27380 KB Output is correct
29 Correct 2020 ms 26244 KB Output is correct
30 Correct 2019 ms 26616 KB Output is correct
31 Correct 2031 ms 26932 KB Output is correct
32 Correct 1993 ms 26600 KB Output is correct
33 Correct 2027 ms 26304 KB Output is correct
34 Correct 2062 ms 27056 KB Output is correct
35 Correct 2025 ms 25424 KB Output is correct
36 Correct 2117 ms 27028 KB Output is correct
37 Correct 2116 ms 27340 KB Output is correct
38 Correct 2143 ms 25772 KB Output is correct
39 Correct 1923 ms 26812 KB Output is correct
40 Correct 1926 ms 25700 KB Output is correct
41 Correct 1911 ms 27272 KB Output is correct
42 Correct 1993 ms 26560 KB Output is correct
43 Correct 1990 ms 28092 KB Output is correct
44 Correct 1984 ms 26400 KB Output is correct
45 Correct 1997 ms 26684 KB Output is correct
46 Correct 1987 ms 26752 KB Output is correct
47 Correct 2029 ms 26872 KB Output is correct
48 Correct 2033 ms 26716 KB Output is correct
49 Correct 2016 ms 26536 KB Output is correct
50 Correct 2027 ms 26748 KB Output is correct