oj.uz

Submission #745165

# Submission time Handle Problem Language Result Execution time Memory
745165 2023-05-19T13:30:32 Z MrBrionix Candies (JOI18_candies) C++17
8 / 100
 630 ms 38872 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;
    if(j<0 || j>=n){exit(0);}
    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 10 ms 596 KB Output is correct
2 Correct 11 ms 552 KB Output is correct
3 Correct 10 ms 640 KB Output is correct
4 Correct 11 ms 528 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 636 KB Output is correct
8 Correct 10 ms 596 KB Output is correct
9 Correct 9 ms 596 KB Output is correct
10 Correct 10 ms 632 KB Output is correct
11 Correct 11 ms 596 KB Output is correct
12 Correct 11 ms 600 KB Output is correct
13 Correct 10 ms 596 KB Output is correct
14 Correct 10 ms 592 KB Output is correct
15 Correct 10 ms 596 KB Output is correct
16 Correct 11 ms 540 KB Output is correct
17 Correct 11 ms 596 KB Output is correct
18 Correct 10 ms 596 KB Output is correct
19 Correct 13 ms 516 KB Output is correct
20 Correct 10 ms 596 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 596 KB Output is correct
2 Correct 11 ms 552 KB Output is correct
3 Correct 10 ms 640 KB Output is correct
4 Correct 11 ms 528 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 636 KB Output is correct
8 Correct 10 ms 596 KB Output is correct
9 Correct 9 ms 596 KB Output is correct
10 Correct 10 ms 632 KB Output is correct
11 Correct 11 ms 596 KB Output is correct
12 Correct 11 ms 600 KB Output is correct
13 Correct 10 ms 596 KB Output is correct
14 Correct 10 ms 592 KB Output is correct
15 Correct 10 ms 596 KB Output is correct
16 Correct 11 ms 540 KB Output is correct
17 Correct 11 ms 596 KB Output is correct
18 Correct 10 ms 596 KB Output is correct
19 Correct 13 ms 516 KB Output is correct
20 Correct 10 ms 596 KB Output is correct
21 Runtime error 630 ms 38872 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -