Public Judge

pjudge

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21760. 【PR #9】选择

统计

给定一个长度为 $n$ 的整数序列 $p_1,\cdots,p_n$ ,以及两个非负整数 $a,b$ 。

对于每个 $1\le k\le n$ ,你需要选出 $p$ 的一个长度为 $k$ 的子序列 $q_1,\cdots,q_k$ ,最大化 $\sum_{i=1}^k q_i(i^2+ai+b)$ 。

输入格式

第一行一个正整数 $T$ ,表示数据组数。每组数据的格式如下:

  • 第一行一个正整数 $n$ 。
  • 第二行 $n$ 个整数 $p_1,\cdots,p_3$ 。
  • 第三行两个正整数 $a,b$ 。

输出格式

对每组数据输出一行 $n$ 个整数,分别表示 $k=1,\cdots,k=n$ 的答案。

样例一

input

2
3
1 2 3
0 0
5
1 -1 1 -1 1
3 2

output

3 14 36
6 18 38 44 26

样例二

见下发文件。

数据范围

对于所有数据,保证 $1\le T\le 20,n\le 50000,|p_i|\le 50000,0\le a,b\le 100,a^2\ge 4b$ 。

子任务编号 特殊限制 分值
$1$ $n\le 3000$ $20$
$2$ $p_i$ 在 $[-50000,50000]$ 均匀随机 $30$
$3$ $T\le 4$ $30$
$4$ $ $ $20$

时间限制:$\texttt{3s}$

空间限制:$\texttt{1024MB}$