AT_abc351_f.[ABC351F] Double Sum

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

给定一个整数序列 $A = (A_1, A_2, \dots, A_N)$ 。
请计算下式的值：

$\sum_{i=1}^N \sum_{j=i+1}^N \max(A_j - A_i, 0)$

在给定的约束条件下，保证答案小于 $2^{63}$ 。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出该式的值。

输入输出样例

输入#1
```
3
2 5 3
```
输出#1
```
4
```
输入#2
```
10
5 9 3 0 4 8 7 5 4 0
```
输出#2
```
58
```

说明/提示

约束

$2 \leq N \leq 4 \times 10^5$
$0 \leq A_i \leq 10^8$
输入的所有值均为整数

样例解释 1

当 $(i, j) = (1, 2)$ 时， $\max(A_j - A_i, 0) = \max(3, 0) = 3$ 。
当 $(i, j) = (1, 3)$ 时， $\max(A_j - A_i, 0) = \max(1, 0) = 1$ 。
当 $(i, j) = (2, 3)$ 时， $\max(A_j - A_i, 0) = \max(-2, 0) = 0$ 。
将这些值相加， $3 + 1 + 0 = 4$ ，即为答案。

由 ChatGPT 4.1 翻译

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

首页