AT2412 最大の和

时间：2021-10-14 08:03:42

传送门

思路：

　　线段树暴力枚举区间，查询最大区间和。

Code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

#include<stack>

#include<vector>

#include<queue>

#include<deque>

#include<map>

#include<set>

using namespace std;

#define lck_max(a,b) ((a)>(b)?(a):(b))

#define lck_min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

const int maxn=1e5+;

const int INF=1e9+;

LL n,k,ans=-INF,sum[maxn<<],a[maxn];

inline LL read()

{

    LL kr=,xs=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

inline void out(LL xs)

{

    if(!xs) {putchar(); return;}

    if(xs<) putchar('-'),xs=-xs;

    int kr[],ls=;

    while(xs) kr[++ls]=xs%,xs/=;

    while(ls) putchar(kr[ls]+),ls--;

}

void build_sum(LL k,LL l,LL r)

{

    if(l==r) {sum[k]=a[l];return;}

    LL mid=l+r>>;

    if(l<=mid) build_sum(k<<,l,mid);

    if(mid<r) build_sum(k<<|,mid+,r);

    sum[k]=sum[k<<]+sum[k<<|];

}

LL query_sum(LL k,LL l,LL r,LL x,LL y)

{

    if(l>=x&&r<=y) return sum[k];

    //if(l>y||r<x) return 0;

    LL mid=l+r>>,res=;

    if(x<=mid) res+=query_sum(k<<,l,mid,x,y);

    if(mid<y) res+=query_sum(k<<|,mid+,r,x,y);

    return res;

}

int main()

{

    n=read();k=read();

    for(LL i=;i<=n;i++) a[i]=read();

    build_sum(,,n);

    for(LL i=k+;i<=n;i++)

        ans=lck_max(ans,query_sum(,,n,i-k+,i));

    out(ans),putchar('\n');

return ;

}

相关文章