Submission #3217094

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

struct SegmentTree {
	std::vector<i64> seg;
	int sz = 1;
	#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

struct Slide_Max {
	std::deque<int> deq;
	std::vector<i64> v;
	int k, i;
	i64 ret;
	
	Slide_Max(int k) : k(k) {
		deq.clear();
		v.clear();
		ret = 0;
		i = 0;
	}
	
	i64 push(i64 x) {
		v.push_back(x);
		while(!deq.empty() and v[deq.back()] <= v[i]) {
			deq.pop_back();
		}
		deq.push_back(i);
		
		ret = v[deq.front()];
		if(deq.front() == i - k + 1) deq.pop_front();
		
		i++;
		return ret;
	}
	
	i64 get() { return (v.size() ? ret : -1); };
};
	
int main(){
	int n, m, k; cin >> n >> m >> k; std::vector<i64> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	
	Slide_Max sm[k + 1](m); sm[0].push(0);
	std::vector<std::vector<i64>> dp(n + 1, std::vector<i64>(k + 1, 0));
	for(int i = 0; i < n; i++) {
		for(i64 j = k - 1; j >= 0; j--) {
			if(sm[j].get() == -1) continue;
			i64 ma = sm[j].get();
			
			dp[i + 1][j + 1] = ma + a[i] * (j + 1);
			sm[j + 1].push(dp[i + 1][j + 1]);
		}
	}
	
	cout << sm[k].get() << endl;
	return 0;
}

	SegmentTree(int n) {
		while(sz < n) sz *= 2;
		seg.assign(sz * 2 - 1, 0);
	}
	
	void update(int k, i64 x) {
		k += sz - 1;
		seg[k] = x;
		
		while(k) {
			k = (k - 1) / 2;
			
			seg[k] = std::max(seg[2 * k + 1], seg[2 * k + 2]);
		}
	}
	
	i64 get(int a, int b, int k, int l, int r) {
		if(r<=a||b<=l) return 0;
		if(a<=l&&r<=b) return seg[k];
		
		return std::max(get(a, b, 2 * k + 1, l, (l + r) / 2), get(a, b, 2 * k + 2, (l + r) / 2, r));
	}
	
	i64 get(int a, int b) {
		return get(a, b, 0, 0, sz);
	}
};

int main(){
	int n, m, k; cin >> n >> m >> k; std::vector<i64> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	
	SegmentTree dp[k + 1](n + 1);
	for(int i = 0; i < n; i++) dp[0].update(i, 1);
	for(int i = 0; i < n; i++) {
		for(i64 j = 0; j < k; j++) {
			i64 tmp = dp[j].get(std::max(0, i - m), i + 1);
			if(!tmp) continue;
			
			dp[j + 1].update(i + 1, tmp + a[i] * (j + 1LL));
		}
	}
	
	cout << dp[k].get(0, n + 1) - 1 << endl;
	return 0;
}

Submission Info

Compile Error

./Main.cpp:11:19: error: declaration of ‘typedef long long int SegmentTree::i64’ [-fpermissive]
 typedef long long i64;
                   ^
./Main.cpp:2:19: error: changes meaning of ‘i64’ from ‘typedef long long int i64’ [-fpermissive]
 typedef long long i64;
                   ^
./Main.cpp:12:12: error: using-declaration for non-member at class scope
 using std::cout;
            ^
./Main.cpp:13:12: error: using-declaration for non-member at class scope
 using std::endl;
            ^
./Main.cpp:14:12: error: using-declaration for non-member at class scope
 using std::cin;
            ^