NOIP的时候一定要看清楚数据范围。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100500
using namespace std;
long long n,k,sum[maxn],dp[maxn],a[maxn],c[maxn],q[maxn],l=,r=,ans=;
int main()
{
scanf("%lld%lld",&n,&k);
for (long long i=;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-]+a[i];
}
c[]=-sum[];
for (long long i=;i<=k;i++)
{
dp[i]=sum[i];ans=max(ans,dp[i]);
c[i+]=dp[i]-sum[i+];
while ((l<=r) && (c[q[r]]<=c[i])) r--;
q[++r]=i;
}
for (long long i=k+;i<=n;i++)
{
while ((l<=r) && (q[l]<i-k)) l++;
dp[i]=c[q[l]]+sum[i];ans=max(ans,dp[i]);
c[i+]=dp[i]-sum[i+];
while ((l<=r) && (c[q[r]]<=c[i])) r--;
q[++r]=i;
}
printf("%lld\n",ans);
return ;
}

最新文章

  1. VMware10.06精简版安装后台运行
  2. windows下Ruby开发环境搭建
  3. hdu 4870 Rating
  4. linux nandflash驱动之MTD层
  5. virtualbox 安装 android 经验总结
  6. (转)最小二乘法拟合圆公式推导及vc实现[r]
  7. kafka消息中间件及java示例
  8. MyBatis框架及原理分析
  9. Python 接口:从协议到抽象基类
  10. dnf命令 (常用总结)
  11. First Unique Character in a String
  12. Spring history、design philosophy (Spring的历史及设计理念)
  13. viewport定义,弹性布局,响应式布局及LESS和SASS框架应用
  14. Python3.4 枚举类型的使用
  15. 软件工程小组讨论设计NABCD
  16. Angular4学习笔记-目录汇总
  17. 面向对象——类的内置attr(三十三)
  18. A - The Water Bowls POJ - 3185 (bfs||高斯消元)
  19. 【java并发核心一】Semaphore 的使用思路
  20. tensorflow使用pb文件进行模型预测

热门文章

  1. js(引用类型和setTimeout scope)
  2. (04)odoo视图操作
  3. HDU----(4549)M斐波那契数列(小费马引理+快速矩阵幂)
  4. 超实用的JavaScript代码段 Item4 --发送短信验证码
  5. SAP本地文件策略(导EXCEL选择拒绝后处理)
  6. 9. shell环境
  7. JQuery时间轴timeline插件的学习-Lateral On-Scroll Sliding with jQuery+technotarek / timeliner
  8. Java JDK的安装以及环境变量的配置
  9. python使用urllib2抓取网页
  10. 标签视图控制器UITabBarController