oj.uz

Submission #745164

# Submission time Handle Problem Language Result Execution time Memory
745164 2023-05-19T13:29:55 Z MrBrionix Candies (JOI18_candies) C++17
8 / 100
 632 ms 38808 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'000'015;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;


template<class F,class D=ll>
vi smawk(F f,int n,int m){
  vi ans(n,-1);
  auto rec=[&](auto self,int*const rs,int x,int*const cs,int y)->void{
    const int t=8;
    if(x<=t||y<=t){
      rep(i,x){
        int r=rs[i];
        D mx;
        rep(j,y){
          int c=cs[j];
          D w=f(r,c);
          if(ans[r]==-1||w>mx){
            ans[r]=c;
            mx=w;
          }
        }
      }
      return;
    }
    if(x<y){
      int s=0;
      rep(i,y){
        int c=cs[i];
        while(s&&f(rs[s-1],cs[s-1])<f(rs[s-1],c))
          s--;
        if(s<x)
          cs[s++]=c;
      }
      y=s;
    }
    auto a=rs+x,b=cs+y;
    int z=0;
    for(int i=1;i<x;i+=2)
      a[z++]=rs[i];
    rep(i,y)
    b[i]=cs[i];
    self(self,a,z,b,y);
    int k=0;
    for(int i=0;i<x;i+=2){
      int to=i+1<x?ans[rs[i+1]]:cs[y-1];
      D mx;
      while(1){
        D w=f(rs[i],cs[k]);
        if(ans[rs[i]]==-1||w>mx){
          ans[rs[i]]=cs[k];
          mx=w;
        }
        if(cs[k]==to)break;
        k++;
      }
    }
  };
  int*rs=new int[n*2];
  rep(i,n)rs[i]=i;
  int*cs=new int[max(m,n*2)];
  rep(i,m)cs[i]=i;
  rec(rec,rs,n,cs,m);
  delete[] rs;
  delete[] cs;
  return ans;
}
template<class T>
vector<T> MaxConvolutionWithConvexShape(vector<T> anyShape, 
  const vector<T> &convexShape) {
  
  if((int) convexShape.size() <= 1) return anyShape;
  if(anyShape.empty()) anyShape.push_back(0);
  int n = (int)anyShape.size(), m = (int)convexShape.size();
  auto function = [&](int i, int j) {
    if(i-j<0 || i-j>=m) return LLONG_MIN;
    assert(j>=0 && j<n);
    return anyShape[j] + convexShape[i-j];
  };
  auto comparator = [&](int i, int j, int k) {
    if(i < k) return false;
    if(i - j >= m) return true;
    return function(i, j) <= function(i, k);
  };
  const vector<int> best = smawk(function, n + m - 1, n);
  vector<T> ans(n + m - 1);
  for(int i = 0; i < n + m - 1; i++)
    ans[i] = function(i, best[i]);
  return ans;
} //$\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 = MaxConvolutionWithConvexShape(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;
  
  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 instantiation of 'std::vector<_Tp> MaxConvolutionWithConvexShape(std::vector<_Tp>, const std::vector<_Tp>&) [with T = long long int]':
candies.cpp:170:75:   required from here
candies.cpp:113:8: warning: variable 'comparator' set but not used [-Wunused-but-set-variable]
  113 |   auto comparator = [&](int i, int j, int k) {
      |        ^~~~~~~~~~
candies.cpp: In lambda function:
candies.cpp:83:26: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |         if(ans[rs[i]]==-1||w>mx){
candies.cpp:80:9: note: 'mx' was declared here
   80 |       D mx;
      |         ^~
candies.cpp:51:24: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |           if(ans[r]==-1||w>mx){
candies.cpp:47:11: note: 'mx' was declared here
   47 |         D mx;
      |           ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 568 KB Output is correct
2 Correct 11 ms 596 KB Output is correct
3 Correct 11 ms 612 KB Output is correct
4 Correct 10 ms 596 KB Output is correct
5 Correct 10 ms 596 KB Output is correct
6 Correct 11 ms 596 KB Output is correct
7 Correct 10 ms 568 KB Output is correct
8 Correct 10 ms 564 KB Output is correct
9 Correct 10 ms 596 KB Output is correct
10 Correct 9 ms 596 KB Output is correct
11 Correct 10 ms 596 KB Output is correct
12 Correct 10 ms 568 KB Output is correct
13 Correct 10 ms 584 KB Output is correct
14 Correct 10 ms 596 KB Output is correct
15 Correct 10 ms 568 KB Output is correct
16 Correct 10 ms 620 KB Output is correct
17 Correct 10 ms 564 KB Output is correct
18 Correct 10 ms 596 KB Output is correct
19 Correct 9 ms 596 KB Output is correct
20 Correct 9 ms 564 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 568 KB Output is correct
2 Correct 11 ms 596 KB Output is correct
3 Correct 11 ms 612 KB Output is correct
4 Correct 10 ms 596 KB Output is correct
5 Correct 10 ms 596 KB Output is correct
6 Correct 11 ms 596 KB Output is correct
7 Correct 10 ms 568 KB Output is correct
8 Correct 10 ms 564 KB Output is correct
9 Correct 10 ms 596 KB Output is correct
10 Correct 9 ms 596 KB Output is correct
11 Correct 10 ms 596 KB Output is correct
12 Correct 10 ms 568 KB Output is correct
13 Correct 10 ms 584 KB Output is correct
14 Correct 10 ms 596 KB Output is correct
15 Correct 10 ms 568 KB Output is correct
16 Correct 10 ms 620 KB Output is correct
17 Correct 10 ms 564 KB Output is correct
18 Correct 10 ms 596 KB Output is correct
19 Correct 9 ms 596 KB Output is correct
20 Correct 9 ms 564 KB Output is correct
21 Runtime error 632 ms 38808 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -