DMOJLand Series: Fake Judges

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

In DMOJLand, when you submit a problem, you assume that a judge is grading a submission. In reality, it is the problem authors who assigned a specific point value for each person when they submit!

bruce has N students in his class. When the i^{th} person submits, they will gain a total of a_i points, where 1 \le i \le N.

Unfortunately, you are submitting to Ninjaclasher's problems, and he wants to minimize the total amount of points bruce's class will obtain.

During the class, the students will submit Q times to Ninjaclasher's problems. For the q^{th} query, 1 \le q \le N, students l_j to r_j will submit and earn their respective points, where the total points they obtain are \sum\limits_{j=l}^{r} A_j, or A_l + A_{l+1} + \dots + A_r.

Before all of the queries are performed, Ninjaclasher can move around the positions of as many students as he would like. Can you help him minimize the total sum of all the queries?

(TLDR; This is why you get low marks on quizzes.)

Input Specification

First line of input will contain 2 integers, N and Q (1 \le N, Q \le 10^5), the size of the class and the number of times the students will submit, respectively.

The second line of input will contain a_i (1 \le a_i \le 10^9), for 1 \le i \le N, the amount of points the i^{th} student will obtain every time he submits.

The next Q lines of input will contain l_i r_i, denoting the range of the students that will submit.


Subtask 1 [30%]

1 \le N, Q, A_i \le 100

l_i = r_i

Subtask 2 [70%]

No additional constraints.

Output Specification

Output the minimum possible sum.

Sample Input 1

4 3
1 2 3 4
2 3
1 4
1 2

Sample Output 1



  • 7
    Dan13llljws  commented on Jan. 5, 2020, 1:34 a.m. edited

    I passed with brute force. I think the test data is too weak. Fix.