LibreOJ #514. 「LibreOJ β Round #2」模拟只会猜题意

　　　　　　　　　　　　　　　　　　　　　　　　内存限制：256 MiB 时间限制：1000 ms 标准输入输出

　　　　　　　　　　　　　　　　　　　　　　　　　　题目类型：传统 评测方式：文本比较

题目描述

给定一个长度为 nnn 的序列 AAA 。

定义 f(l,r)=∑i=lrAif(l,r)=\sum_{i=l}^{r} A_{i}f(l,r)=∑​i=l​r​​A​i​​。

询问 mmm 次，每次询问一个数字 xxx，请求出所有满足 r−l+1≥xr-l+1 \ge xr−l+1≥x 区间 [l,r][l,r][l,r] 中最大的 f(l,r)f(l,r)f(l,r)。

输入格式

第一行两个数，表示 nnn 和 mmm 。
之后 nnn 个数，表示序列 AAA。
之后 mmm 行每行一个数 xxx，表示询问 xxx 。

输出格式

输出 mmm 行，每行一个答案，表示最大的 f(l,r)f(l,r)f(l,r) 。

样例

样例输入

5 5

1 2 3 4 5

1

2

3

4

5

样例输出

15

15

15

15

15

数据范围与提示

前缀和就好

屠龙宝刀点击就送

#include <cstring>

#include <cstdio>

#define N 10005

int sum[N],maxn[N],n,m;

inline int max(int a,int b) {return a>b?a:b;}

int main()

{

    memset(maxn,-0x3f,sizeof(maxn));

    scanf("%d%d",&n,&m);

    for(int a,i=;i<=n;++i)

     scanf("%d",&a),sum[i]=sum[i-]+a;

    for(int i=;i<=n;++i)

     for(int j=;j<=i;++j)

      maxn[i-j+]=max(maxn[i-j+],sum[i]-sum[j-]);

    for(int i=;i<=n;++i)

     for(int j=i+;j<=n;++j)

      maxn[i]=max(maxn[i],maxn[j]);

    for(int x;m--;)

    {

        scanf("%d",&x);

        printf("%d\n",maxn[x]);

    }

    return ;

}