Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int main()
- {
- /*
- given a n*m matrix (image), q users to use that software.
- every user -> Input->choose a submatrix output->sum of that submatrix.
- 4 5
- 2 3 1 4 5
- 1 2 3 4 5
- 0 2 3 0 1
- 1 0 4 0 8
- 3
- 1 1 2 3 -> 14
- 1 2 3 3 -> 14
- 2 2 2 2 -> 3
- */
- int n, m; cin >> n >> m;//rows and colms
- vector<vector<int>> v(n, vector<int>(m));//2d vector
- for (int i = 0; i < n; i++) {//input matrix
- for (int j = 0; j < m; j++) {
- cin >> v[i][j];
- }
- }
- // int q; cin >> q;//users
- // while (q--) {
- // int a, b, c, d; cin >> a >> b >> c >> d;//input param for each user
- // int tempans = 0;
- // for (int i = a; i <= c; i++) {//ans calculated
- // for (int j = b; j <= d; j++) {
- // tempans += v[i][j];
- // }
- // }
- // cout << "User ans -> " << tempans << endl;
- // }
- //t.c-> O(Q*N*M)-->O(N^3)
- vector<vector<int>> p(n + 1, vector<int>(m + 1, 0));//prefix matrix;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- p[i][j] = v[i - 1][j - 1] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
- }
- }
- for (int i = 0; i <= n; i++) {
- for (int j = 0; j <= m; j++) {
- cout << p[i][j] << " ";
- }
- cout << endl;
- }
- // 2 3 1 4 5
- // 1 2 3 4 5
- // 0 2 3 0 1
- // 1 0 4 0 8
- // 0 0 0 0 0 0
- // 0 2 5 6 10 15
- // 0 3 8 12 20 30
- // 0 3 10 17 25 36
- // 0 4 11 22 30 49
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement