Official

E - 飛び石の最小コスト / Minimum Cost of Stepping Stones Editorial by physics0523

AI 生成の解説のようにスライド最小値を用いて時間計算量を \(O(N)\) にすることもできます。
あるいは、 SWAG と呼ばれるデータ構造を使っても時間計算量を \(O(N)\) にすることができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

// DSWAG (SWAG-deque) (based on ACL segtree)
// https://motsu-xe.hatenablog.com/entry/2019/12/06/192424
// https://qiita.com/Shirotsume/items/4a2837b5895ef9a7aeb1#%E7%B5%82%E3%82%8F%E3%82%8A%E3%81%AB

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct DSWAG {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct DSWAG {

#endif

  public:
    explicit DSWAG(){
      hel=stack<S>();
      tel=stack<S>();
      hop=stack<S>();
      top=stack<S>();
    }
    void push_front(S x){
      hel.push(x);
      if(hop.empty()){
        hop.push(x);
      }
      else{
        hop.push(op(x,hop.top()));
      }
    }
    void push_back(S x){
      tel.push(x);
      if(top.empty()){
        top.push(x);
      }
      else{
        top.push(op(top.top(),x));
      }
    }
    void pop_front(){
      if(hel.empty()){
        vector<S> kp(tel.size());
        for(int i=kp.size()-1;i>=0;i--){
          kp[i]=tel.top(); tel.pop(); top.pop();
        }
        int tl=(kp.size()+1)/2;
        for(int i=tl-1;i>=0;i--){
          if(hel.empty()){
            hel.push(kp[i]);
            hop.push(kp[i]);
          }
          else{
            hel.push(kp[i]);
            hop.push(op(kp[i],hop.top()));
          }
        }
        for(int i=tl;i<kp.size();i++){
          if(tel.empty()){
            tel.push(kp[i]);
            top.push(kp[i]);
          }
          else{
            tel.push(kp[i]);
            top.push(op(top.top(),kp[i]));
          }
        }
      }
      hel.pop();
      hop.pop();
    }
    void pop_back(){
      if(tel.empty()){
        vector<S> kp(hel.size());
        for(int i=0;i<kp.size();i++){
          kp[i]=hel.top(); hel.pop(); hop.pop();
        }
        int tl=(kp.size())/2;
        for(int i=tl-1;i>=0;i--){
          if(hel.empty()){
            hel.push(kp[i]);
            hop.push(kp[i]);
          }
          else{
            hel.push(kp[i]);
            hop.push(op(kp[i],hop.top()));
          }
        }
        for(int i=tl;i<kp.size();i++){
          if(tel.empty()){
            tel.push(kp[i]);
            top.push(kp[i]);
          }
          else{
            tel.push(kp[i]);
            top.push(op(top.top(),kp[i]));
          }
        }
      }
      tel.pop();
      top.pop();
    }
    S get(){
      if(hop.empty() && top.empty()){return e();}
      else if(hop.empty()){return top.top();}
      else if(top.empty()){return hop.top();}
      return op(hop.top(),top.top());
    }
  private:
    stack<S> hel,tel,hop,top;
};

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

ll op(ll x,ll y){return min(x,y);}
ll e(){return 4e18;}

int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll> a(n);
  for(auto &nx : a){cin >> nx;}
  DSWAG<ll,op,e> sw;
  sw.push_back(a[0]);
  for(ll i=1;i<n;i++){
    ll val=sw.get()+a[i];
    if(i==n-1){
      cout << val << "\n";
      return 0;
    }
    sw.push_back(val);
    if(i>=k){sw.pop_front();}
  }
  return 0;
}