张鑫杰 @ 2018-10-24 19:09:01
#include<bits/stdc++.h>
#define ini(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define F(x,y,z) for(register int x=y;x<=z;++x)
#define D(x,y,z) for(register int x=y;x>=z;--x)
#define cint const int&
using namespace std;
const int MAXN=static_cast<int>(1e5)+100;
const long long INF=0x3f3f3f3f3f3f3f3f;
const int oo=0x3f3f3f3f;
#define int long long
inline int read()
{
int x = 0, y = 1, c = getchar();
while (c>'9' || c<'0')
{
if (c == '-')y = -1;
c = getchar();
}
while (c >= '0'&&c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * y;
};
int data[MAXN];
struct node{
int data,pos;
node(int d=0,int p=0){
data=d;
pos=p;
}
};
class Deque{
private:
//#define node int
node que[MAXN];
int head=0,tail=0,_size=0;
const int MOD=2e5+1;
public:
void push_back(const node&i){
que[tail++]=i;
_size++;
tail%=MOD;
}
void push_front(const node&i){
que[--head]=i;
_size++;
head%=MOD;
}
void pop_back(){
tail--;
_size--;
tail%=MOD;
}
void pop_front(){
head++;
_size--;
head%=MOD;
}
node front(){
return que[head];
}
node back(){
return que[tail-1];
}
int size(){
return _size;
}
bool empty(){
return !_size;
}
//#undef node
};
Deque q;
int sum[MAXN],f[MAXN][2];
signed main(){
int n=read(),k=read();
F(i,1,n){
sum[i]=sum[i-1]+read();
}
F(i,1,n){
f[i][0]=max(f[i-1][0],f[i-1][1]);
while(!q.empty()&&q.front().pos<=i-k){
q.pop_front();
}
f[i][1]=((q.empty())?0:q.front().data)+sum[i];
while(!q.empty()&&q.back().data<=f[i][0]-sum[i]){
q.pop_back();
}
q.push_back(node(i,f[i][0]-sum[i]));
//cout<<f[i][0]<<" "<<f[i][1]<<endl;
}
printf("%lld",max(f[n][0],f[n][1]));
return 0;
}
会选择超出k的值,我表示很奇怪的
by あおあんどん @ 2018-10-24 19:10:35
抱歉,我才学两年,我也不会
by 高天宇 @ 2018-10-24 19:16:24
不给装弱者看题,这句话对吧。
by 求败 @ 2018-10-24 19:20:10
不给装弱者看题,这句话对吧。
by niolle @ 2018-10-24 19:24:04
不给装弱者看题,这句话对吧。
by 张鑫杰 @ 2018-10-24 19:26:39
@handsome·zlk ......
by 张鑫杰 @ 2018-10-24 19:27:33
我还是调不出来
by 张鑫杰 @ 2018-10-24 19:43:06
....
by 在想Peach @ 2019-01-20 21:11:25
我信你个鬼,~~你这个糟老头子坏的很~~
by _xcc_ @ 2019-01-25 15:06:29
考古