1 solutions

  • 0
    @ 2023-2-20 21:21:03
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 300010, INF = 0x3f3f3f3f;
    
    int n, m;
    int s[N], q[N];
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ )
        {
            scanf("%d", &s[i]);
            s[i] += s[i - 1];
        }
    
        int res = -INF;
        int hh = 0, tt = 0;
        for (int i = 1; i <= n; i ++ )
        {
            if (q[hh] < i - m) hh ++ ;
            res = max(res, s[i] - s[q[hh]]);
            while (hh <= tt && s[q[tt]] >= s[i]) tt -- ;
            q[ ++ tt] = i;
        }
    
        printf("%d\n", res);
    
        return 0;
    }

    Information

    ID
    6695
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    8
    Tags
    # Submissions
    80
    Accepted
    4
    Uploaded By