题目详情题解（0）讨论（0）提交记录（0）

AT_abc407_f.[ABC407F] Sums of Sliding Window Maximum

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你一个长度为 NN 的数列 A=(A1,…,AN)A=(A_1,\dots,A_N)，请对于所有 1≤k≤N1\le k\le N 求解下面的问题：

  • 求出 AA 长为 kk 的全部 N−k+1N-k+1 个连续子序列的最大值的和。

输入格式

将按照以下格式输入：

NN

A1A_1 $ A_2$ A3A_3 …\dots ANA_N

输出格式

NN 行，第 ii 行为 k=ik=i 时所求解问题的答案。

输入输出样例

  • 输入#1

    4
5 3 4 2

    输出#1

    14
13
9
5

  • 输入#2

    8
2 0 2 5 0 5 2 4

    输出#2

    20
28
27
25
20
15
10
5

  • 输入#3

    11
9203973 9141294 9444773 9292472 5507634 9599162 497764 430010 4152216 3574307 430010

    输出#3

    61273615
68960818
69588453
65590626
61592799
57594972
47995810
38396648
28797486
19198324
9599162

说明/提示

数据规模与约定

  • 1≤N≤2×1051 \le N \le 2 \times 10^{5}
  • 0≤Ai≤107(1≤i≤N)0 \le A_i \le 10^{7} (1 \le i \le N)
  • 输入的所有数字为整数。

输入解题思路，AI测评打分。不知道怎么写?

首页