Advertisement
GastonFontenla

Untitled

May 19th, 2017
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. int main()
  8. {
  9.     vector <vector <int> > matriz;
  10.     int n, m;
  11.     cin >> n >> m;
  12.     matriz = vector <vector <int> > (n, vector <int> (m));
  13.     ///N filas y M columnas
  14.  
  15.     for(int i=0; i<n; i++)
  16.     {
  17.         for(int j=0; j<m; j++)
  18.         {
  19.             cin >> matriz[i][j]; ///Leo la matriz
  20.         }
  21.     }
  22.  
  23.     vector <vector <int> > dp(n+1, vector <int> (m+1));
  24.  
  25.     for(int i=0; i<n+1; i++) ///Lleno la primer columna de cero
  26.         dp[i][0] = 0;
  27.  
  28.     for(int j=0; j<m+1; j++) ///Lleno la primer fila de cero
  29.         dp[0][j] = 0;
  30.  
  31.  
  32.     for(int i=0; i<n; i++)
  33.     {
  34.         for(int j=0; j<m; j++)
  35.         {
  36.             int celdaArriba = dp[i][j+1];
  37.             int celdaIzquierda = dp[i+1][j];
  38.             int celdaDiagonal = dp[i][j];
  39.             int celdaMatrizInput = matriz[i][j];
  40.  
  41.             dp[i+1][j+1] =  celdaArriba + celdaIzquierda - celdaDiagonal + celdaMatrizInput;
  42.         }
  43.     }
  44.  
  45.     int consultas;
  46.  
  47.     cin >> consultas; ///La cantidad de consultas que me hacen
  48.  
  49.     for(int i=0; i<consultas; i++)
  50.     {
  51.         int x1, y1;
  52.         int x2, y2;
  53.         cin >> x1 >> y1 >> x2 >> y2; ///Leo el rango de la consultaa
  54.  
  55.         int celdaFin = dp[x2+1][y2+1];
  56.         int celda1 = dp[x1][y2+1];
  57.         int celda2 = dp[x2+1][y1];
  58.         int celda3 = dp[x1][y1];
  59.  
  60.         int r = celdaFin - celda1 - celda2 + celda3;
  61.         cout << "La suma es " << r << endl;
  62.     }
  63.  
  64.     /**
  65.     Input:
  66.     6 5
  67.     1 2 3 4 5
  68.     -3 2 0 5 8
  69.     3 9 8 0 5
  70.     9 1 0 2 3
  71.     8 1 1 -10 6
  72.     0 3 5 6 0
  73.     5
  74.     3 3 5 4
  75.     0 0 5 4
  76.     0 0 0 0
  77.     0 0 5 0
  78.     0 0 0 4
  79.     **/
  80.  
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement