codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

740B.md (2955B)


      1 Source: https://codeforces.com/problemset/problem/740/B
      2 
      3 B. Alyona and flowers
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Little Alyona is celebrating Happy Birthday! Her mother has an array of *n* flowers. Each flower has some mood, the mood of *i*-th flower is *a**i*. The mood can be positive, zero or negative.
     22 
     23 Let's define a subarray as a segment of consecutive flowers. The mother suggested some set of subarrays. Alyona wants to choose several of the subarrays suggested by her mother. After that, each of the flowers will add to the girl's happiness its mood multiplied by the number of chosen subarrays the flower is in.
     24 
     25 For example, consider the case when the mother has 5 flowers, and their moods are equal to 1,  - 2, 1, 3,  - 4. Suppose the mother suggested subarrays (1,  - 2), (3,  - 4), (1, 3), (1,  - 2, 1, 3). Then if the girl chooses the third and the fourth subarrays then:
     26 
     27 * the first flower adds 1·1 = 1 to the girl's happiness, because he is in one of chosen subarrays,
     28 * the second flower adds ( - 2)·1 =  - 2, because he is in one of chosen subarrays,
     29 * the third flower adds 1·2 = 2, because he is in two of chosen subarrays,
     30 * the fourth flower adds 3·2 = 6, because he is in two of chosen subarrays,
     31 * the fifth flower adds ( - 4)·0 = 0, because he is in no chosen subarrays.
     32 
     33 Thus, in total 1 + ( - 2) + 2 + 6 + 0 = 7 is added to the girl's happiness. Alyona wants to choose such subarrays from those suggested by the mother that the value added to her happiness would be as large as possible. Help her do this!
     34 
     35 Alyona can choose any number of the subarrays, even 0 or all suggested by her mother.
     36 
     37 Input
     38 
     39 The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 100) — the number of flowers and the number of subarrays suggested by the mother.
     40 
     41 The second line contains the flowers moods — *n* integers *a*1, *a*2, ..., *a**n* ( - 100 ≤ *a**i* ≤ 100).
     42 
     43 The next *m* lines contain the description of the subarrays suggested by the mother. The *i*-th of these lines contain two integers *l**i* and *r**i* (1 ≤ *l**i* ≤ *r**i* ≤ *n*) denoting the subarray *a*[*l**i*], *a*[*l**i* + 1], ..., *a*[*r**i*].
     44 
     45 Each subarray can encounter more than once.
     46 
     47 Output
     48 
     49 Print single integer — the maximum possible value added to the Alyona's happiness.
     50 
     51 Examples
     52 
     53 Input
     54 
     55 ```
     56 5 4  
     57 1 -2 1 3 -4  
     58 1 2  
     59 4 5  
     60 3 4  
     61 1 4
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 7
     68 ```
     69 
     70 Input
     71 
     72 ```
     73 4 3  
     74 1 2 3 4  
     75 1 3  
     76 2 4  
     77 1 1
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 16
     84 ```
     85 
     86 Input
     87 
     88 ```
     89 2 2  
     90 -1 -2  
     91 1 1  
     92 1 2
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 0
     99 ```
    100 
    101 Note
    102 
    103 The first example is the situation described in the statements.
    104 
    105 In the second example Alyona should choose all subarrays.
    106 
    107 The third example has answer 0 because Alyona can choose none of the subarrays.