AT_kupc2019_f.カズマ王国の陥落

通过率：0%

AC君温馨提醒

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

题目描述

在卡兹玛王国中，有 $N$ 个城镇，每个城镇中住着一位勇者。

第 $i(1≤i≤N)$ 城镇中的勇者最多可以击败 $A_i$ 只怪兽。勇者们渴望获得经验值，因此会尽可能多地击败前来自己城镇的怪兽。

你是魔王，在统治下有 $M$ 个据点。第 $j(1 ≤ j ≤ M)$ 个据点可以自由地派遣 $B_j$ 只怪兽到第 $L_j, L_j+1, ...,R_j-1, R_j$ 个城镇。未被勇者击败的怪兽数量将给予卡兹玛王国造成伤害。

请计算卡兹玛王国所受到的最大总伤害。

输入格式

第一行，有一个数 $N$ 表示城镇个数。

第二行，有 $N$ 个整数 $A_1,A_2,...,A_n$ 表示每个城镇中的勇者最多可以击败的怪兽个数。

第三行，有一个整数 $M$ 表示据点个数。

接下来的 $M$ 行，第 $j$ 行有三个整数 $L_j,R_j,B_j$ ，描述了第 $j$ 个据点的 $L,R,B$ 。

输出格式

请输出卡兹玛王国所受到的最大总伤害。

输入输出样例

输入#1
```
4
5 4 3 4
3
2 3 7
1 2 4
3 4 3
```
输出#1
```
7
```
输入#2
```
3
4 7 5
3
1 2 3
2 3 2
1 3 5
```
输出#2
```
4
```

输入#3

10
9 7 4 11 5 100 95 3 55 12
12
2 3 6
1 2 2
1 4 8
3 5 5
3 5 6
4 4 6
5 7 3
5 8 5
1 10 52
9 10 13
7 9 2
8 9 5

输出#3

输入#4

1
1
10
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

输出#4

9999999999

说明/提示

输入均为整数。
$ 1 \leq N \leq 3000 $
$ 1 \leq M \leq 3000 $
$ 1 \leq A_i \leq 10^9 $
$ 1 \leq B_j \leq 10^9 $
$ 1 \leq L_j \leq R_j \leq N $

样例解释 1

如果按照以下方式派遣，可以给卡兹玛王国造成总共 $7$ 点伤害：

从第 $1$ 个据点派遣 $5$ 只怪兽到第 $2$ 个城镇， $2$ 只怪兽到第 $3$ 个城镇。
从第 $2$ 个据点派遣 $4$ 只怪兽到第 $2$ 个城镇。
从第 $3$ 个据点各派遣 $3$ 只怪兽到第 $3$ 个城镇。

样例解释 4

请注意防止溢出。

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

首页