假期（codevs 3622）

题目描述 Description

经过几个月辛勤的工作，FJ决定让奶牛放假。假期可以在1…N天内任意选择一段（需要连续），每一天都有一个享受指数W。但是奶牛的要求非常苛刻，假期不能短于P天，否则奶牛不能得到足够的休息；假期也不能超过Q天，否则奶牛会玩的腻烦。FJ想知道奶牛们能获得的最大享受指数。

输入描述 Input Description

第一行：N,P,Q.

第二行：N个数字，中间用一个空格隔开。

输出描述 Output Description

一个整数，奶牛们能获得的最大享受指数。

样例输入 Sample Input

5 2 4

-9 -4 -3 8 -6

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

50% 1≤N≤10000

100% 1≤N≤100000

１<=p<=q<=n

指数在longint范围之内。

提示：

选择第3-4天，享受指数为-3+8=5

/*

  50分的做法是对于每个s[i]，找到最小的s[j](i-x<=j<=i-y)，更新答案。

  由于这个j是在一段区间内的，所以可以用单调队列优化。

*/

#include<cstdio>

#include<iostream>

#define N 100010

#define INF 10000000000000LL

#define ll long long

using namespace std;

ll a[N],s[N],q[N],n,x,y,head=,tail;

int main()

{

    cin>>n>>x>>y;

    for(ll i=;i<=n;i++)

    {

        ll p;cin>>p;

        s[i]=s[i-]+p;

    }

    ll ans=-INF;

    for(ll i=x;i<=n;i++)

    {

        while(s[i-x]<s[q[tail]]&&head<=tail)tail--;

        q[++tail]=i-x;

        while(q[head]<i-y&&head<=tail)head++;

        ans=max(ans,s[i]-s[q[head]]);

    }

    cout<<ans;

    return ;

}