The_Law

Untitled

Dec 26th, 2018
533
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector< vector<int> > d; //массив для динамики
  7.  
  8. int get_sum(int x1, int x2, int y1, int y2)
  9. {
  10.     if (x1 == 1 && y1 == 1) {
  11.         return d[x2][y2];
  12.     } else if (x1 == 1) {
  13.         return d[x2][y2] - d[x2][y1 - 1];
  14.     } else if (y1 == 1) {
  15.         return d[x2][y2] - d[x1 - 1][y2];
  16.     } else {
  17.         return d[x2][y2] - d[x2][y1 - 1] - d[x1 - 1][y2] + d[x1 - 1][y1 - 1];
  18.     }
  19. }
  20.  
  21. int main()
  22. {
  23.     int n;
  24.     cin >> n;
  25.  
  26.     vector< vector<int> > a(n, vector<int> (n)); //данная матрица
  27.     d.resize(n + 1, vector<int> (n + 1));
  28.  
  29.     for (int i = 0; i < n; ++i) {
  30.         for (int j = 0; j < n; ++j)
  31.             cin >> a[i][j];
  32.     }
  33.    
  34.     for (int i = 1; i < n + 1; ++i) {
  35.         d[i][1] = a[i - 1][0] + d[i - 1][1];
  36.         d[1][i] = a[0][i - 1] + d[1][i - 1];
  37.     }
  38.  
  39.     for (int i = 2; i < n + 1; ++i) {
  40.         for (int j = 2; j < n + 1; ++j) {
  41.             d[i][j] = d[i - 1][j] + d[i][j - 1] + a[i - 1][j - 1] - d[i - 1][j - 1];
  42.         }
  43.     }
  44.  
  45.     int max_sum = -1e9;
  46.  
  47.     for (int x1 = 1; x1 < n + 1; ++x1) {
  48.         for (int x2 = x1; x2 < n + 1; ++x2) {
  49.             for (int y1 = 1; y1 < n + 1; ++y1) {
  50.                 for (int y2 = y1; y2 < n + 1; ++y2) {
  51.                     max_sum = max(max_sum, get_sum(x1, x2, y1, y2));
  52.                 }
  53.             }
  54.         }
  55.     }
  56.  
  57.     cout << max_sum << endl;
  58.  
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment