提出 #54734937

---

ソースコード 拡げる

#include <iostream>
using namespace std;

#include <atcoder/segtree>
using namespace atcoder;

using P = pair<long long,long long>;

P op(P a,P b){
  return {max(a.first,b.first),min(a.second,b.second)};
}
P e(){
  return {-1e18,1e18};
}

// https://noshi91.hatenablog.com/entry/2023/02/18/005856
// T は辺コストの型
// cost(i,j) は頂点 i -> 頂点 j へのコスト(型 T)を返す関数
// 頂点番号は 0-ind
// 返り値は配列 dist で dist[i] が 0 -> i の最小コストに相当
// a[i][j] を j -> i を最後にするコスト dist[j]+cost(j,i) とする(j < i)
// a[i] が最小値を取るような j が欲しい これを amin で管理
template <typename T,typename F>
vector<T> monge_shortest_path(int n,T inf,const F & cost){
  vector<T> dist(n,inf);
  dist[0]=0;
  vector<int> amin(n,0);

  auto check=[&](int i,int k){
    // k -> i に行くもので暫定の最小値を更新できるかを確認
    if(k>=i)return;
    auto dist2=dist[k]+cost(k,i);
    if(dist2<dist[i]){
      dist[i]=dist2;
      amin[i]=k;
    }
  };

  auto subsolve=[&](auto& subsolve,int l,int r){
    // (l,r] について dist を計算する
    if(r-l==1)return;
    int m=(l+r)/2;
    for(int k=amin[l];k<=amin[r];k++)check(m,k);
    subsolve(subsolve,l,m);
    for(int k=l+1;k<=m;k++)check(r,k);
    subsolve(subsolve,m,r);
  };

  check(n-1,0);
  subsolve(subsolve,0,n-1);
  return dist;
}

int main(){
  int n;cin>>n;
  vector<long long> a(n);
  for(int i=0;i<n;i++)cin>>a[i];

  segtree<P,op,e> seg(n);
  for(int i=0;i<n;i++)seg.set(i,{a[i],a[i]});

  auto cost=[&](int i,int j){
    auto [mx,mn]=seg.prod(i,j);
    return mn-mx;
  };

  auto dist=monge_shortest_path<long long>(n+1,1e18,cost);
  cout<<-dist[n]<<endl;
}

提出情報

ジャッジ結果