提出 #73588789

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define oke cout << "Yes" << '\n';
#define dame cout << "No" << '\n';
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using Hai2 = vector<vector<ll>>;
using HaiW = vector<vector<pair<ll,ll>>>;
using HaiB = vector<vector<bool>>;
using Hai3 = vector<vector<vector<ll>>>;

ll gousei(ll A,ll B){//セグ木を一段上にする
	return max(A,B);
}

ll kousin(ll A,ll B){//元々Aだったものを何とかする 加算の時はA+B
	return max(A,B);
}

ll e(){//初期値
	return -1e18;
}

//0インデックスで関数に入れる
//追加の変数名注意　fは既にある
struct segment{
    vector<ll>seg;
    ll seg_size=1;

	segment(ll N){
		while(N>seg_size){
            seg_size*=2;
        }
        seg.resize(seg_size*2);
        rep(i,seg_size*2){
            seg[i]=e();
        }
	}

    void update(ll X,ll Y){
        X+=seg_size;
        seg[X]=kousin(seg[X],Y);

        ll f=X/2;
        while(f>0){
            seg[f]=gousei(seg[f*2],seg[f*2+1]);
            f/=2;
        }
    }

    ll query(ll l,ll r){
        return naka_query(0,seg_size-1,l,r,1);
    }
    //a以上b以下　L＝０　R＝seg_size-1　v=1で関数に入れる
    ll naka_query(ll L,ll R,ll a,ll b,ll v){
        if(a<=L && R<=b) return seg[v];

        //ここも変える
        if(b<L || R<a) return e();

        ll T=0;
        ll mid=(L+R)/2;
        T=gousei(naka_query(L,mid,a,b,v*2),naka_query(mid+1,R,a,b,v*2+1));

        return T;
    }
};

int main() {
	cout << fixed << setprecision(15);
    ll N,K;
    cin>>N>>K;
    vector<ll>A(N);
    rep(i,N){
        cin>>A[i];
    }

    segment DP(N);
    DP.update(0,A[0]);
    for(ll i=1;i<N;i++){
        ll l=max(0LL,i-K);
        ll r=i-1;
        ll v=DP.query(l,r)+A[i];
        DP.update(i,v);
    }
    cout<<DP.query(N-1,N-1)<<endl;
}

提出情報

ジャッジ結果