oj.uz

Submission #745241

# Submission time Handle Problem Language Result Execution time Memory
745241 2023-05-19T15:28:09 Z MrBrionix Candies (JOI18_candies) C++17
100 / 100
 2164 ms 23116 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 = conv(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 instantiation of 'std::vector<int> smawk(int, int, const Select&) [with Select = conv<long long int>::<lambda(int, int, int)>]':
candies.cpp:51:33:   required from 'std::vector<_Tp> conv(const std::vector<_Tp>&, const std::vector<_Tp>&) [with T = long long int]'
candies.cpp:103:50:   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: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];
      |                    ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 544 KB Output is correct
2 Correct 20 ms 660 KB Output is correct
3 Correct 19 ms 468 KB Output is correct
4 Correct 18 ms 524 KB Output is correct
5 Correct 19 ms 520 KB Output is correct
6 Correct 18 ms 556 KB Output is correct
7 Correct 18 ms 544 KB Output is correct
8 Correct 21 ms 544 KB Output is correct
9 Correct 17 ms 468 KB Output is correct
10 Correct 18 ms 540 KB Output is correct
11 Correct 19 ms 556 KB Output is correct
12 Correct 20 ms 640 KB Output is correct
13 Correct 18 ms 724 KB Output is correct
14 Correct 18 ms 596 KB Output is correct
15 Correct 17 ms 500 KB Output is correct
16 Correct 17 ms 564 KB Output is correct
17 Correct 17 ms 468 KB Output is correct
18 Correct 18 ms 532 KB Output is correct
19 Correct 18 ms 468 KB Output is correct
20 Correct 17 ms 516 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 544 KB Output is correct
2 Correct 20 ms 660 KB Output is correct
3 Correct 19 ms 468 KB Output is correct
4 Correct 18 ms 524 KB Output is correct
5 Correct 19 ms 520 KB Output is correct
6 Correct 18 ms 556 KB Output is correct
7 Correct 18 ms 544 KB Output is correct
8 Correct 21 ms 544 KB Output is correct
9 Correct 17 ms 468 KB Output is correct
10 Correct 18 ms 540 KB Output is correct
11 Correct 19 ms 556 KB Output is correct
12 Correct 20 ms 640 KB Output is correct
13 Correct 18 ms 724 KB Output is correct
14 Correct 18 ms 596 KB Output is correct
15 Correct 17 ms 500 KB Output is correct
16 Correct 17 ms 564 KB Output is correct
17 Correct 17 ms 468 KB Output is correct
18 Correct 18 ms 532 KB Output is correct
19 Correct 18 ms 468 KB Output is correct
20 Correct 17 ms 516 KB Output is correct
21 Correct 2128 ms 22652 KB Output is correct
22 Correct 2144 ms 22840 KB Output is correct
23 Correct 2164 ms 21192 KB Output is correct
24 Correct 1980 ms 22816 KB Output is correct
25 Correct 1974 ms 21668 KB Output is correct
26 Correct 1951 ms 21188 KB Output is correct
27 Correct 2051 ms 20916 KB Output is correct
28 Correct 1991 ms 21364 KB Output is correct
29 Correct 1989 ms 22944 KB Output is correct
30 Correct 2007 ms 21244 KB Output is correct
31 Correct 2009 ms 23116 KB Output is correct
32 Correct 1999 ms 21780 KB Output is correct
33 Correct 2039 ms 21928 KB Output is correct
34 Correct 2027 ms 22376 KB Output is correct
35 Correct 2005 ms 21228 KB Output is correct
36 Correct 2136 ms 21744 KB Output is correct
37 Correct 2114 ms 20888 KB Output is correct
38 Correct 2117 ms 21464 KB Output is correct
39 Correct 1914 ms 21676 KB Output is correct
40 Correct 1947 ms 22796 KB Output is correct
41 Correct 1899 ms 21280 KB Output is correct
42 Correct 1995 ms 20916 KB Output is correct
43 Correct 1986 ms 21656 KB Output is correct
44 Correct 2000 ms 21180 KB Output is correct
45 Correct 2021 ms 23108 KB Output is correct
46 Correct 1994 ms 21408 KB Output is correct
47 Correct 2044 ms 21040 KB Output is correct
48 Correct 2044 ms 21296 KB Output is correct
49 Correct 2029 ms 22612 KB Output is correct
50 Correct 2029 ms 20880 KB Output is correct