codeforces-scrape

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

120D.md (2078B)


      1 Source: https://codeforces.com/problemset/problem/120/D
      2 
      3 D. Three Sons
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 input.txt
     16 
     17 output
     18 
     19 output.txt
     20 
     21 Three sons inherited from their father a rectangular corn fiend divided into *n* × *m* squares. For each square we know how many tons of corn grows on it. The father, an old farmer did not love all three sons equally, which is why he bequeathed to divide his field into three parts containing *A*, *B* and *C* tons of corn.
     22 
     23 The field should be divided by two parallel lines. The lines should be parallel to one side of the field and to each other. The lines should go strictly between the squares of the field. Each resulting part of the field should consist of at least one square.
     24 
     25 Your task is to find the number of ways to divide the field as is described above, that is, to mark two lines, dividing the field in three parts so that on one of the resulting parts grew *A* tons of corn, *B* on another one and *C* on the remaining one.
     26 
     27 Input
     28 
     29 The first line contains space-separated integers *n* and *m* — the sizes of the original (1 ≤ *n*, *m* ≤ 50, *max*(*n*, *m*) ≥ 3). Then the field's description follows: *n* lines, each containing *m* space-separated integers *c**ij*, (0 ≤ *c**ij* ≤ 100) — the number of tons of corn each square contains. The last line contains space-separated integers *A*, *B*, *C* (0 ≤ *A*, *B*, *C* ≤ 106).
     30 
     31 Output
     32 
     33 Print the answer to the problem: the number of ways to divide the father's field so that one of the resulting parts contained *A* tons of corn, another one contained *B* tons, and the remaining one contained *C* tons. If no such way exists, print 0.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 3 3  
     41 1 1 1  
     42 1 1 1  
     43 1 1 1  
     44 3 3 3
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 2
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 2 5  
     57 1 1 1 1 1  
     58 2 2 2 2 2  
     59 3 6 6
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 3
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 3 3  
     72 1 2 3  
     73 3 1 2  
     74 2 3 1  
     75 5 6 7
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 0
     82 ```
     83 
     84 Note
     85 
     86 The lines dividing the field can be horizontal or vertical, but they should be parallel to each other.