比赛 |
20110414 |
评测结果 |
WAWWWWWWAWWAAWW |
题目名称 |
奶牛的跳格子游戏 |
最终得分 |
26 |
用户昵称 |
kaaala |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-04-14 09:11:11 |
显示代码纯文本
#include<fstream>
#include<cmath>
#include<cstdlib>
#include<string>
using namespace std;
long long f[250011],v[250011],sum[250011],p[250011],q[250011],ans=0;
long n,k;
long long mx(long long a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
long i,l,r;
ifstream fin("hop.in");
ofstream fout("hop.out");
fin>>n>>k;
for(i=1;i<=n;i++)
fin>>v[i];
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++)
sum[i]=sum[i-1]+mx(v[i],0);
v[n+1]=0;
l=1;
r=1;
q[1]=0;
p[1]=0;
f[0]=0;
for(i=1;i<=n;i++)
{
if(p[1]==0)
while((l<=r)&&(i-p[1]>=k))
l++;
else
while((l<=r)&&(i-p[1]>k))
l++;
f[i]=q[1]+v[i+1]+sum[i-1]+v[i];
while((l<=r)&&(q[r]<=(f[i]-sum[i+1])))
r--;
r++;
q[r]=f[i]-sum[i+1];
p[r]=i;
}
for(i=1;i<=n;i++)
if(f[i]-v[i+1]>ans)
ans=f[i]+v[i+1];
fout<<ans;
fin.close();
fout.close();
return 0;
}