Submission #2423091

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-6;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

/*
int main(void){
	int32 N;
	cin >> N;
	vector<int64> v(N);
	REP(i, N) cin >> v[i];

	int64 maxi = 0;
	int64 res = 0;
	REP(i, N){
		int64 cnt = (v[i]-1)/(maxi+1);
		if(cnt){ res += cnt; chmax(maxi, 1); }
		else maxi = v[i];
	}
	cout << res << endl;
}
*/

class RMQ{
private:
	int32 n;
	vector<int64> node, lazy;
	vector<bool> lazyFlag;
public:
	RMQ(vector<int64> v){
		int sz = v.size();
		n = 1; while(n < sz) n *= 2;
		node.resize(2*n-1, -INF_LL);
		lazy.resize(2*n-1, 0);
		lazyFlag.resize(2*n-1, false);
		for(int32 i = 0;i < sz;i++) node[i+n-1] = v[i];
		for(int32 i = n-2;i >= 0;i--) node[i] = max(node[2*i+1], node[2*i+2]);
	}

	void eval(int32 k, int32 l, int32 r){
		if(lazyFlag[k]){
			node[k] = lazy[k];
			if(r-l > 1){
				lazy[2*k+1] = lazy[k];
				lazy[2*k+2] = lazy[k];
				lazyFlag[2*k+1] = lazyFlag[2*k+2] = true;
			}
			lazy[k] = 0;
			lazyFlag[k] = false;
		}
	}

	void update(int32 k, int64 x){
		k += n-1;
		if(node[k] > x) return;
		node[k] = x;
		while(k){
			k = (k-1)/2;
			node[k] = max(node[k*2+1], node[k*2+2]);
		}
	}

	int64 query(int32 a, int32 b, int32 k=0, int32 l=0, int32 r=-1){
		if(r < 0) r = n;
//		eval(k, l, r);

		if(b <= l || r <= a) return -INF_LL;
		if(a <= l && r <= b) return node[k];

		return max(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
	}
};

int main(void){
	int32 M, N, K;
	cin >> N >> M >> K;
	vector<int64> A(N);
	vector<RMQ> rmq(K+1, RMQ(vector<int64>(N+1, 0)));
	REP(i, N) cin >> A[i];

	REP(i, N){
		REP(j, K){
			rmq[j+1].update(i+1, rmq[j].query(max((int32)0, i-M+1), i+1)+A[i]*(j+1));
		}
	}
	cout << rmq[K].query(0, N+1) << endl;
}

Submission Info

Judge Result