P7867Aurora的刷题计划 | ||
|
问题描述
题目背景
Aurora AK IOI everyday!
题目描述
Aurora放寒假了!(Au rora,指金牌rora)
它决定利用寒假的时间好好刷题,争取明年不止AKIOI,而是AKZJOI!
何老板非常支持Aurora的想法。寒假一共有 \(n(1\le n\le 2\times 10^6)\) 天,何老板给Aurora每天都安排了一道题,由Aurora自己选择刷不刷这道题,但是Aurora实在是太强了,有些题对于Aurora来说太水了,反而会降低它的水平。
第 \(i\) 天的题目难度系数为 \(w_i\)(\(-10^6\le w_i\le 10^6\))。每刷一道难度系数为 \(x\) 的题,Aurora的水平就会增加 \(x\)。由于Aurora过于强大,你可以认为他的初始水平是无限的。但是,在别人都在努力学习的寒假,Aurora只要连续 \(k\) 天不刷题,他的水平就会减少 \(k^2\)。
Aurora和何老板当然都希望整个寒假都结束后,Aurora的水平尽量高。现在,Aurora把安排整个寒假的刷题计划这个光荣,伟大,艰难,辉煌的使命交给了你,问你整个寒假结束后Aurora水平最多能提高多少(有可能存在Aurora无论如何整个寒假过后水平都会降低情况,这个时候输出应为负数)。
输入格式
第一行,一个整数 \(n\),表示整个寒假的天数。
第二行,\(n\) 个用空格间隔的整数,表示每道题目的 \(w_i\)。
输出格式
输出仅一行,一个整数,表示Aurora的水平最大能提高多少。
样例输入 1
5
-5 -5 -5 -5 -5
样例输出 1
-13
样例输入 2
8
1 -3 4 -2 1 0 -1 1
样例输出 2
4
样例输入 3
1
-10000
样例输出 3
-1
提示
对于样例一,在第三天刷题,则前两天没刷题,水平降低 $2^{2}=4$,后两天没刷题,水平降低 $2^{2}=4$,然后第三天的题目难度为 \(-5\),水平总共提高 \(-5-4-4=-13\)。
样例二,刷 $1,3,5,6,8$ 天的题。
样例三,一道题不刷。
测试点编号 | 数据范围 | 特殊性质 |
---|---|---|
$1,2$ | \(n\le 5000\) | 无 |
$3$ | \(n\le 10^6\) | \(w_i\) 均为非负数 |
$4$ | \(n\le 10^4\) | 无 |
$5,6$ | \(n\le 2\times 10^4\) | 无 |
$7,8$ | \(n\le 5\times 10^4\) | 无 |
$9,10$ | \(n\le 10^5\) | 无 |
$11$ | \(n\le 10^5\) | \(w_i\) 均为负数 |
$12,13$ | \(n\le 2\times 10^5\) | 无 |
$14,15$ | \(n\le 5\times 10^5\) | 无 |
$16$ | \(n\le 10^6\) | 无 |
$17\sim 20$ | \(n\le 2\times 10^6\) | 无 |