暴力60pts记录

单调队列0pts记录

#include <iostream>
#include <cstring>
#include <deque>
using namespace std;

const int N = 2e5 + 10,M = 50;
int n,p,Q,c,d,f[N][M],ans[N][M],a[N],sum[N];
deque <int> q;

void print(int x,int y)
{
	if (!y) return ;
	print(ans[x][y],y - 1);
	cout << ans[x][y] + 1 << ' ';
}

int get(int x,int y)
{ return f[y][x - 1] + a[y + 1] - sum[y + c]; }

int main()
{
	ios::sync_with_stdio(0);
	cin >> p >> Q >> c >> d;
	n = p * c + Q;
	for(int i = 1;i <= n;i ++)
		cin >> a[i],sum[i] = sum[i - 1] + a[i];
	memset(f,-0x3f,sizeof(f));
	f[0][0] = 0;
	for(int i = 1;i <= d;i ++) f[i][0] = sum[i];
	for(int j = 1;j <= p;j ++)
	{
		while (!q.empty()) q.pop_back();
		for(int k = max(0,j * c - c - d);k <= j * c - c;k ++)
		{
			while (!q.empty() && get(j,q.back()) <= get(j,k)) q.pop_back();
			q.push_back(k);
//			cout << "OK" << endl;
		}
		for(int i = j * c;i <= n;j ++)
		{
			while (!q.empty() && q.front() < max(0,i - c - d)) q.pop_front();
			if (!q.empty()) f[i][j] = get(j,q.front()) + sum[i],ans[i][j] = q.front();
			int k = i + 1 - c;
			while (!q.empty() && get(j,q.back()) <= get(j,k)) q.pop_back();
			q.push_back(k);
		}
	}
	cout << f[n][p] << endl;
	print(n,p);
	return 0;
}