Question Name:GOLD MINES

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int r,c,mod=pow(10,9)+7;
    cin>>r>>c;
    int64_t a[r][c];
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
            cin>>a[i][j];
    }
    for(int i=1;i<r;i++)
    {
        a[i][0]=a[i-1][0]+a[i][0];
    }
    for(int i=1;i<c;i++)
    {
        a[0][i]=a[0][i-1]+a[0][i];
    }
    for(int i=1;i<r;i++)
    {
        for(int j=1;j<c;j++)
        {
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    int q;
    cin>>q;
    int f,g,h,k;
    while(q--)
    {
        cin>>f>>g>>h>>k;
        f--;g--;h--;k--;
        int64_t sum=a[h][k];
        if(f!=0&&g!=0)
        {
            sum=sum+a[f-1][g-1]-a[h][g-1]-a[f-1][k];
        }
        else if(f!=0)
        {
            sum=sum-a[f-1][k];
        }
        else if(g!=0)
        {
            sum=sum-a[h][g-1];
        }
        cout<<sum<<"\n";
    }
}
  • Problem Description
    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
  • Test Case 1
    Input (stdin)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
    Expected Output31
    14
    47
    7
  • Test Case 2
    Input (stdin)4 4
    2 4 9 7
    4 8 1 7
    5 7 3 4
    4 8 7 4
    4
    1 2 4 2
    1 4 2 4
    1 1 4 2
    2 4 2 4
    Expected Output27
    14
    42
    7

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro