一本通1598【例 2】最大连续和

1598：【例 2】最大连续和

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

给你一个长度为 $n$

【输入】

第一行为两个整数 $n, m$

第二行为 $n$

【输出】

仅一个整数，表示连续长度不超过 $m$

【输入样例】

6 4
1 -3 5 1 -2 3

【输出样例】

【提示】

数据范围与提示：

对于 50% 的数据， $1 \leq N, M \leq 10^{4}$

对于 100% 的数据， $1 \leq N, M \leq 2 \times 10^{5}$

$1 \leq N, M \leq 2 \times 10^{5}$

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-');
        ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
inline void writeln(ll x)
{
    write(x);
    putchar('
');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) writeln(x)
const int N=200005,inf=0x3f3f3f3f;
int n,m,Qzh[N];
struct Record
{
    int Shuz,Weiz;
}Ddq[N];
int main()
{
//    freopen("sum12.in","r",stdin);
    int i,Head=0,Tail=0,ans=-inf;
    R(n); R(m);
    for(i=1;i<=n;i++)
    {
        int x=read(); Qzh[i]=Qzh[i-1]+x;
        while(Head<Tail&&Ddq[Head].Weiz<i-m) Head++;
        ans=max(ans,Qzh[i]-Ddq[Head].Shuz);
        while(Head<=Tail&&Qzh[i]<=Ddq[Tail].Shuz) Tail--;
        Ddq[++Tail]=(Record){Qzh[i],i};
    }
    Wl(ans);
    return 0;
}
/*
input
5 2
-21 -2 -1 -11 -3
output
-1
*/

View Code

一本通1598【 例 2】最大连续和

1598：【 例 2】最大连续和