AtCoder Beginner Contest 421
翻译中…
Problem Statement
翻译中…
You are given a length-$N$ integer sequence $A=(A_1,A_2,\ldots,A_N)$. You are also given $M$ pairs of integers $(L_1, R_1), (L_2, R_2), \dots, (L_M, R_M)\ (1\leq L_i\leq R_i\leq N)$.
翻译中…
You can perform the following operation on sequence $A$ any number of times (possibly zero):
翻译中…
- Choose an integer
$i$with$1 \leq i \leq M$, and add$1$to each of$A_{L_i}, A_{L_i+1},\dots, A_{R_i}$.
翻译中…
Determine whether it is possible to make $A$ non-decreasing, and if possible, find the minimum number of operations required.
翻译中…
Constraints
翻译中…
$1\leq N \leq 300$$1\leq M \leq 300$$1\leq A_i \leq 300$$1\leq L_i\leq R_i\leq N$- All input values are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N M
A_1 A_2 \dots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M翻译中…
Output
翻译中…
If it is possible to make $A$ non-decreasing, print the minimum number of operations required. If it is impossible, print -1.
翻译中…
样例
Input #1
4 3
4 2 3 2
2 2
2 3
4 4
Output #1
4
For example, by performing operations four times as follows, you can make $A$ non-decreasing:
- Choose $i=1$ and perform the operation. $A$ becomes $(4,3,3,2)$.
- Choose $i=3$ and perform the operation. $A$ becomes $(4,3,3,3)$.
- Choose $i=3$ and perform the operation. $A$ becomes $(4,3,3,4)$.
- Choose $i=2$ and perform the operation. $A$ becomes $(4,4,4,4)$.
Conversely, it is impossible to make $A$ non-decreasing with three or fewer operations. Thus, print $4$.
Input #2
3 2
3 1 2
2 2
1 2
Output #2
-1
No matter how you perform operations, it is impossible to make $A$ non-decreasing.
Input #3
4 4
1 1 2 3
1 1
2 2
3 3
4 4
Output #3
0
$A$ is already non-decreasing, so no operations are needed.
Input #4
8 12
35 29 36 88 58 15 25 99
5 5
1 6
3 8
8 8
4 8
7 7
5 7
3 3
2 6
1 6
6 7
5 7
Output #4
79
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。