/ SB域 /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 2ms 2.191 MiB
#2 Accepted 1ms 2.199 MiB
#3 Accepted 1ms 2.199 MiB
#4 Accepted 2ms 2.324 MiB
#5 Accepted 12ms 2.672 MiB
#6 Accepted 24ms 3.043 MiB
#7 Accepted 35ms 1.445 MiB
#8 Accepted 48ms 3.812 MiB
#9 Accepted 62ms 3.656 MiB
#10 Accepted 52ms 3.852 MiB

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
 
int N, Min, Max;
int MAX = -999999999 + 5;
int Q[500050];
int sum[500050];
 
void init_file()
{
    freopen("max.in", "r", stdin);
    freopen("max.out", "w", stdout);
}
 
void read_data()
{
    scanf("%d%d%d", &N, &Min, &Max);
    for(int i = 1; i <= N; i++)
    {
        int x;
        scanf("%d", &x);
        sum[i] = sum[i - 1] + x;
    }
}
 
void work()
{
    int l = 0;
    int r = 0;
    r ++;
    Q[r] = 0;
    int ans = -0x3f3f3f3f;
    for(int i = Min; i <= N; i++)
    {
        while(l<r && i - Q[l+1] > Max) l++;
        while(l<r && sum[Q[r]]>=sum[i-Min]) r--;
        Q[++r] = i-Min;
        ans = max(ans,sum[i]-sum[Q[l+1]]);
    }
    printf("%d",ans);
}
 
int main()
{
    read_data();
    work();
    return 0;
}

信息

递交者
类型
递交
题目
【模板】最大子序和
题目数据
下载
语言
C++
递交时间
2019-10-01 08:35:55
评测时间
2019-10-01 08:35:55
评测机
分数
100
总耗时
246ms
峰值内存
3.852 MiB