比赛 |
20110414 |
评测结果 |
AWWWWWWWWAWWAWA |
题目名称 |
奶牛的跳格子游戏 |
最终得分 |
26 |
用户昵称 |
Pom |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-04-14 09:32:38 |
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN=260000;
const long long oo=1000000000000000LL;
struct xds
{
int l,r;
long long c;
xds *cl,*cr;
}T[MAXN*2],*root;
int i,j,k,a[MAXN],x,y,ps,n;
long long f[MAXN],ans,t,sum[MAXN];
void mkt(xds *p,int l,int r)
{
p->l=l;
p->r=r;
p->c=0;
if (r>l)
{
int mid=(l+r)>>1;
++ps;
p->cl=T+ps;
mkt(p->cl,l,mid);
++ps;
p->cr=T+ps;
mkt(p->cr,mid+1,r);
}
}
void cha(xds *p)
{
if (p->r<x || p->l>y) return;
if (p->l>=x && p->r<=y)
{
if (p->c>t)
{
t=p->c;
}
return;
}
cha(p->cl);
cha(p->cr);
}
void ins(xds *p)
{
if (p->r<i || p->l>i) return;
if (p->l==p->r)
{
p->c=f[i]+sum[n]-sum[i];
return;
}
ins(p->cl);
ins(p->cr);
p->c=max(p->cl->c,p->cr->c);
}
int main()
{
freopen("hop.in","r",stdin);
freopen("hop.out","w",stdout);
scanf("%d%d",&n,&k);
sum[0]=0;
if (k==0)
{
printf("0\n");
return 0;
}
root=T;
mkt(root,0,n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1];
if (a[i]>0) sum[i]+=a[i];
}
if (k==1)
{
cout<<max(0,a[1])<<endl;
return 0;
}
ans=0;
i=0;
f[0]=0;
ins(root);
i=1;
f[1]=a[1];
ins(root);
for (i=2;i<=n;i++)
{
x=max(i-k,0);
y=i-2;
t=-oo;
cha(root);
f[i]=a[i]+a[i-1]+t-(sum[n]-sum[i-2]);
ins(root);
if (f[i]>ans) ans=f[i];
}
cout<<ans<<endl;
return 0;
}