oj.uz

Submission #745211

# Submission time Handle Problem Language Result Execution time Memory
745211 2023-05-19T14:56:13 Z MrBrionix Candies (JOI18_candies) C++17
100 / 100
 2318 ms 23388 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;

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:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i != a2.size(); i += 1)
      |                     ~~^~~~~~~~~~~~
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:58: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:110:74:   required from here
candies.cpp:21:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   21 |       if (c2.size() < n)
      |           ~~~~~~~~~~^~~
candies.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i != a2.size(); i += 1)
      |                     ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 544 KB Output is correct
2 Correct 18 ms 468 KB Output is correct
3 Correct 20 ms 464 KB Output is correct
4 Correct 18 ms 444 KB Output is correct
5 Correct 18 ms 524 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 568 KB Output is correct
9 Correct 16 ms 468 KB Output is correct
10 Correct 17 ms 524 KB Output is correct
11 Correct 18 ms 544 KB Output is correct
12 Correct 18 ms 484 KB Output is correct
13 Correct 19 ms 616 KB Output is correct
14 Correct 18 ms 468 KB Output is correct
15 Correct 17 ms 548 KB Output is correct
16 Correct 25 ms 540 KB Output is correct
17 Correct 18 ms 468 KB Output is correct
18 Correct 18 ms 536 KB Output is correct
19 Correct 18 ms 544 KB Output is correct
20 Correct 17 ms 552 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 544 KB Output is correct
2 Correct 18 ms 468 KB Output is correct
3 Correct 20 ms 464 KB Output is correct
4 Correct 18 ms 444 KB Output is correct
5 Correct 18 ms 524 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 568 KB Output is correct
9 Correct 16 ms 468 KB Output is correct
10 Correct 17 ms 524 KB Output is correct
11 Correct 18 ms 544 KB Output is correct
12 Correct 18 ms 484 KB Output is correct
13 Correct 19 ms 616 KB Output is correct
14 Correct 18 ms 468 KB Output is correct
15 Correct 17 ms 548 KB Output is correct
16 Correct 25 ms 540 KB Output is correct
17 Correct 18 ms 468 KB Output is correct
18 Correct 18 ms 536 KB Output is correct
19 Correct 18 ms 544 KB Output is correct
20 Correct 17 ms 552 KB Output is correct
21 Correct 2172 ms 23116 KB Output is correct
22 Correct 2146 ms 21256 KB Output is correct
23 Correct 2139 ms 21564 KB Output is correct
24 Correct 1910 ms 23388 KB Output is correct
25 Correct 1928 ms 21676 KB Output is correct
26 Correct 1969 ms 21276 KB Output is correct
27 Correct 2029 ms 21472 KB Output is correct
28 Correct 2035 ms 21500 KB Output is correct
29 Correct 2045 ms 23328 KB Output is correct
30 Correct 1999 ms 21580 KB Output is correct
31 Correct 2007 ms 23180 KB Output is correct
32 Correct 2005 ms 23248 KB Output is correct
33 Correct 2011 ms 22332 KB Output is correct
34 Correct 1992 ms 23048 KB Output is correct
35 Correct 2076 ms 21332 KB Output is correct
36 Correct 2149 ms 21304 KB Output is correct
37 Correct 2157 ms 21760 KB Output is correct
38 Correct 2120 ms 21700 KB Output is correct
39 Correct 1880 ms 21744 KB Output is correct
40 Correct 1881 ms 23180 KB Output is correct
41 Correct 1889 ms 21496 KB Output is correct
42 Correct 2047 ms 21128 KB Output is correct
43 Correct 1995 ms 22288 KB Output is correct
44 Correct 1968 ms 21448 KB Output is correct
45 Correct 2069 ms 23276 KB Output is correct
46 Correct 2156 ms 21600 KB Output is correct
47 Correct 2242 ms 21372 KB Output is correct
48 Correct 2208 ms 21468 KB Output is correct
49 Correct 2163 ms 22888 KB Output is correct
50 Correct 2318 ms 21188 KB Output is correct