Advertisement
maycod23

Untitled

Feb 22nd, 2023
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5. /*
  6.  
  7. given a n*m matrix (image), q users to use that software.
  8. every user -> Input->choose a submatrix output->sum of that submatrix.
  9.  
  10. 4 5
  11. 2 3 1 4 5
  12. 1 2 3 4 5
  13. 0 2 3 0 1
  14. 1 0 4 0 8
  15. 3
  16. 1 1 2 3 -> 14
  17. 1 2 3 3 -> 14
  18. 2 2 2 2 -> 3
  19.  
  20.  
  21. */
  22. int n, m; cin >> n >> m;//rows and colms
  23. vector<vector<int>> v(n, vector<int>(m));//2d vector
  24. for (int i = 0; i < n; i++) {//input matrix
  25. for (int j = 0; j < m; j++) {
  26. cin >> v[i][j];
  27. }
  28. }
  29.  
  30. // int q; cin >> q;//users
  31. // while (q--) {
  32. // int a, b, c, d; cin >> a >> b >> c >> d;//input param for each user
  33. // int tempans = 0;
  34. // for (int i = a; i <= c; i++) {//ans calculated
  35. // for (int j = b; j <= d; j++) {
  36. // tempans += v[i][j];
  37. // }
  38. // }
  39. // cout << "User ans -> " << tempans << endl;
  40. // }
  41.  
  42. //t.c-> O(Q*N*M)-->O(N^3)
  43.  
  44. vector<vector<int>> p(n + 1, vector<int>(m + 1, 0));//prefix matrix;
  45. for (int i = 1; i <= n; i++) {
  46. for (int j = 1; j <= m; j++) {
  47. p[i][j] = v[i - 1][j - 1] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
  48. }
  49. }
  50.  
  51.  
  52. for (int i = 0; i <= n; i++) {
  53. for (int j = 0; j <= m; j++) {
  54. cout << p[i][j] << " ";
  55. }
  56. cout << endl;
  57. }
  58.  
  59.  
  60.  
  61.  
  62. // 2 3 1 4 5
  63. // 1 2 3 4 5
  64. // 0 2 3 0 1
  65. // 1 0 4 0 8
  66.  
  67. // 0 0 0 0 0 0
  68. // 0 2 5 6 10 15
  69. // 0 3 8 12 20 30
  70. // 0 3 10 17 25 36
  71. // 0 4 11 22 30 49
  72.  
  73. return 0;
  74.  
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement