Submission #1721141

---

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
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<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 a[100001];
int n,m,k;
ll dp[100001][301];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>k;
	for(int i = 0; i < n; i++)
	{
		cin>>a[i];
	}
	for(int i = 0; i < n; i++)
	{
		dp[i][1] = a[i];
	}
	ll sum = a[0];
	for(int j = 2; j <= k; j++)
	{
		deque<ll> dq;
		dp[j-1][j] = sum+ll(j)*a[j-1];
		sum=dp[j-1][j];
		for(int z = 0; z < j; z++)
		{
			while(!dq.empty()&&dp[dq.back()][j-1]<=dp[z][j-1]) dq.pop_back();
			dq.push_back(z);
		}	
		for(int i = j; i < n; i++)
		{
			dp[i][j] = ll(j)*a[i] + dp[dq.front()][j-1];
			while(!dq.empty()&&dp[dq.back()][j-1]<=dp[i][j-1]) dq.pop_back();
			dq.push_back(i);
			while(!dq.empty()&&i-dq.front()>=m) dq.pop_front();
		}
	}
	ll ans = 0;
	for(int i = 0; i < n; i++) ans = max(ans, dp[i][k]);
	cout<<ans<<'\n';
}

Submission Info

Judge Result