Submission #1864658

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e17

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll ball[111111], dp[111111][333];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++){
		cin >> ball[i];
		dp[i][1]=ball[i];
	}
	deque <ii> cur;
	for(int j = 2; j <= k; j++){
		cur.clear();
		for(int i = 1; i <= n; i++){
			while(!cur.empty()){
				if(i-cur[0].fi>m){
					cur.pop_front();
				}
				else{
					break;
				}
			}
			if(i<j){
				dp[i][j]=-INF;
			}
			else{				
				dp[i][j]=cur[0].se+j*ball[i];
			}
			while(!cur.empty()){
				if(dp[i][j-1]>cur[cur.size()-1].se){
					cur.pop_back();
				}
				else{
					break;
				}
			}
			cur.pb(mp(i,dp[i][j-1]));
		}
	}
	ll ans = -INF;
	for(int i = 1; i <= n; i++){
		ans=max(ans,dp[i][k]);
	}
	cout <<ans<<'\n';
	return 0;
}

Submission Info

Judge Result