Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int main()
- {
- vector <vector <int> > matriz;
- int n, m;
- cin >> n >> m;
- matriz = vector <vector <int> > (n, vector <int> (m));
- ///N filas y M columnas
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<m; j++)
- {
- cin >> matriz[i][j]; ///Leo la matriz
- }
- }
- vector <vector <int> > dp(n+1, vector <int> (m+1));
- for(int i=0; i<n+1; i++) ///Lleno la primer columna de cero
- dp[i][0] = 0;
- for(int j=0; j<m+1; j++) ///Lleno la primer fila de cero
- dp[0][j] = 0;
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<m; j++)
- {
- int celdaArriba = dp[i][j+1];
- int celdaIzquierda = dp[i+1][j];
- int celdaDiagonal = dp[i][j];
- int celdaMatrizInput = matriz[i][j];
- dp[i+1][j+1] = celdaArriba + celdaIzquierda - celdaDiagonal + celdaMatrizInput;
- }
- }
- int consultas;
- cin >> consultas; ///La cantidad de consultas que me hacen
- for(int i=0; i<consultas; i++)
- {
- int x1, y1;
- int x2, y2;
- cin >> x1 >> y1 >> x2 >> y2; ///Leo el rango de la consultaa
- int celdaFin = dp[x2+1][y2+1];
- int celda1 = dp[x1][y2+1];
- int celda2 = dp[x2+1][y1];
- int celda3 = dp[x1][y1];
- int r = celdaFin - celda1 - celda2 + celda3;
- cout << "La suma es " << r << endl;
- }
- /**
- Input:
- 6 5
- 1 2 3 4 5
- -3 2 0 5 8
- 3 9 8 0 5
- 9 1 0 2 3
- 8 1 1 -10 6
- 0 3 5 6 0
- 5
- 3 3 5 4
- 0 0 5 4
- 0 0 0 0
- 0 0 5 0
- 0 0 0 4
- **/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement