TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7867
  • 题目
  • P7867Aurora的刷题计划
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,128m
    问题描述

    题目背景

    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\)