All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Gold Mines
Tag(s):

Algorithms, Dynamic Programming, Easy

Problem
Editorial
Analytics

There is a rectangular grid of gold mine. The grid has R rows and C columns. So it has R*C cells in total. The rows are numbered from 1 to R and the columns are numbered from 1 to C. The top most row has number 1, the row next to it has number 2 and so on. Similarly, the left most column has number 1, the column next to it has number 2 and so on. Each cell in the grid has a unique coordinate which is (x, y) where x is the row number and y is the column number of that particular cell.

Each cell in the grid has certain amount of gold in it. Total gold in a sub rectangle of the grid is the sum of all units of gold contained in the cells that are inside the rectangle. Your task is to find the total gold in the given sub rectangle.

A sub rectangle of the grid is defined by four integers x1, y1, x2 and y2. A cell (x, y) belongs to the sub rectangle if and only if x1 <= x <= x2 and y1 <= y <=y2

Input
First line of the input contains two space separated integers, R and C. It is followed by R lines, each line has C space separated integers. Each integer denotes the units of gold present in that particular cell.
Next line has number Q, it is followed by Q queries each query in a single line. Each query is four space separated integers x1, y1, x2 and y2.

Output
For each query, you have to print a single number the total gold contained in that sub rectangle.

Constraints
1 <= R <= 1000
1 <= C <= 1000
1 <= x1 <= x2 <= R
1 <= y1 <= y2 <= C
Amount of gold in each cell is an integer from 0 to 10^6

SAMPLE INPUT
4 4
2 8 9 7
5 8 1 7
5 7 3 5
4 8 7 4
4
1 2 4 2
1 4 2 4
1 1 4 2
2 4 2 4
SAMPLE OUTPUT
31
14
47
7
Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

SmartOwner Services

Challenge Name

Angelprime Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications