【题解】  

  手残写错调了好久QAQ......

  洛谷的数据似乎比较水。。

  n个正整数!!这很重要

  这道题是个类似two pointer的思想,外加一个单调队列维护当前区间内长度为d的子序列中元素之和的最大值。

  枚举右端点,如果左端点到右端点的元素和减去区间内长为d的子序列中元素和的最大值,大于给定的P,那么就把左端点向右挪。

  

#include<cstdio>
#include<algorithm>
#define N 2000010
#define rg register
#define LL long long
using namespace std;
LL n,m,d,a[N],h[N],s[N],p[N],tmp;
int ans;
inline LL read(){
LL k=0; char c=getchar();
while(c<'0'||c>'9')c=getchar();
while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
return k;
}
inline int max(int x,int y){
return x>y?x:y;
}
int main(){
n=read(); m=read(); ans=d=read();
for(rg int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i];
if(n<=d) return printf("%d\n",d),0;
int l=1,front=1,rear=0;
for(rg int i=d+1;i<=n;i++){
tmp=s[i]-s[i-d];
while(front<=rear&&h[rear]<=tmp) rear--;
h[++rear]=tmp; p[rear]=i-d+1;
while(p[front]<l&&front<=rear) front++;
while(l<=i-d+1){
if(front<=rear) tmp=s[i]-s[l-1]-h[front];
else tmp=s[i]-s[l-1];
if(tmp<=m){
ans=max(ans,i-l+1);
break;
}
else l++;
}
tmp=s[i]-s[l-1];
}
printf("%d\n",ans);
return 0;
}

  

最新文章

  1. 幼儿园的 selenium
  2. Python测试函数的方法之一
  3. C#微信公众平台接入示例代码
  4. 【转】 jquery遍历json数组方法
  5. 通过viewmodel找到view
  6. Node.js项目目录介绍
  7. visual studio 插件开发
  8. NeHe OpenGL教程 第十八课:二次几何体
  9. 【 UVALive - 4287】Proving Equivalences (SCC缩点)
  10. poj 1204 Word Puzzles(字典树)
  11. OO第二次博客作业--第二单元总结
  12. 给opencart产品页添加额外信息
  13. MySQL Limit优化(转)
  14. vim 文本会在末尾自动添加换行 md5文件和数据只不对应
  15. chattr和lsattr命令的使用(对于root用户也无法修改删除的操作问题)
  16. 基于jQuery遮罩图片hover翻转效果
  17. Ubuntu 16.04下deb文件的安装
  18. 曲演杂坛--HASH的一点理解
  19. **PHP foreach 如何判断为数组最后一个最高效?
  20. NuGet学习笔记(1) 初识NuGet及快速安装使用[转]

热门文章

  1. 解决juqery easyui combobox只能选择问题
  2. bzoj 1631: [Usaco2007 Feb]Cow Party【spfa】
  3. P4244 [SHOI2008]仙人掌图 II
  4. extjs grid禁止表格头部使用鼠标拖拽改变宽度
  5. Classic BADI总结
  6. 关于Anaconda环境变量配置遇到的一些情况说明
  7. SeasLog的日志
  8. 各种轮播实现(纯css实现+js实现)
  9. [译]HTTP POSTing
  10. WCF学习笔记(2)-WCF的通讯过程