比赛 |
20110414 |
评测结果 |
AAAAWAAWAAAWAAA |
题目名称 |
奶牛的跳格子游戏 |
最终得分 |
80 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-04-14 11:03:59 |
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;
typedef long long s64;
const s64 MAXN=250005;
const s64 oo=~0ull>>3;
s64 N,K;
s64 sum[MAXN];
s64 d[MAXN];
s64 w[MAXN];
bool in[MAXN];
int main()
{
freopen("hop.in","r",stdin);
freopen("hop.out","w",stdout);
cin>>N>>K;
for(s64 i=1;i<=N;i++)
{
cin>>w[i];
if (w[i]>0) sum[i]=sum[i-1]+w[i];
else sum[i]=sum[i-1];
}
if (K==1 || N==1)
{
if (w[1]>0) cout<<w[1]<<endl;
else cout<<0<<endl;
return 0;
}
for(s64 i=0;i<=N;i++)
d[i]=-oo;
s64 re=0;
for(s64 i=2;i<=K;i++)
d[i]=w[i]+w[i-1]+sum[i-2];
if (sum[K-1]>0)
d[K+1]=w[K+1]+w[K]+sum[K-1];
else
{
d[K+1]=-oo;
for(s64 i=1;i<=K+1-2;i++)
if (w[i]>d[K+1])
d[K+1]=w[i];
d[K+1]+=w[K+1]+w[K];
}
deque<pair<s64,s64> >q;
q.push_back(make_pair(d[2]-sum[2],2));
in[2]=true;
for(s64 i=3;i<=N;i++)
{
s64 l=max(s64(2),i-K);
while(q.size() && q.front().second<l)
q.pop_front();
if (i-2>=l && !in[i-2])
{
in[i-2]=true;
s64 j=i-2;
s64 nd=d[j]-sum[j];
while(q.size() && q.back().first<nd)
q.pop_back();
q.push_back(make_pair(nd,i-2));
}
s64 nd=q.front().first+w[i]+w[i-1]+sum[i-2];
if (nd>d[i])
d[i]=nd;
/*
for(s64 j=max(2,i-K);j<=i-2;j++)
{
s64 nd=d[j]+sum[i-2]-sum[j]+w[i]+w[i-1];
if (nd>d[i])
d[i]=nd;
}*/
}
for(s64 i=2;i<=N;i++)
if (d[i]+sum[min(i-1+K,N)]-sum[i]>re)
re=d[i]+sum[min(i-1+K,N)]-sum[i];
cout<<re<<endl;
return 0;
}