Advertisement
Guest User

Untitled

a guest
Mar 29th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. vector<vector<int> > build_sum_table(vector<vector<int> > table) {
  6.     vector<vector<int> > sum_table = {};
  7.     for (int i = 0; i < table.size(); i++) {
  8.         vector<int> sum_line = {0};
  9.         for (int j = 0; j < table[0].size(); j++) {
  10.             sum_line.push_back(sum_line[j] + table[i][j]);
  11.         }
  12.         sum_table.push_back(sum_line);
  13.     }
  14.     return sum_table;
  15. }
  16.  
  17. int find_sum(vector<vector<int> > sum_table, int x1, int x2, int y) {
  18.     return sum_table[y][x2 + 1] - sum_table[y][x1];
  19. }
  20.  
  21. int find_gsum(vector<vector<int> > table) {
  22.     vector<vector<int> > sum_table = build_sum_table(table);
  23.     int gsum = table[0][0];
  24.     for (int x2 = 0; x2 < table[0].size(); x2++) {
  25.         for (int x1 = 0; x1 <= x2; x1++) {
  26.             int imax = find_sum(sum_table, x1, x2, 0);
  27.             for (int y = 1; y < table.size(); y++) {
  28.                 imax += find_sum(sum_table, x1, x2, y);
  29.                 if (find_sum(sum_table, x1, x2, y) > imax) {
  30.                     imax = find_sum(sum_table, x1, x2, y);
  31.                 }
  32.                 if (imax > gsum) {
  33.                     gsum = imax;
  34.                 }
  35.             }
  36.         }
  37.     }
  38.     return gsum;
  39. }
  40.  
  41. int main() {
  42.  
  43.     int n;
  44.     cin >> n;
  45.     vector<vector<int> > table = {};
  46.     for (int i = 0; i < n; i++) {
  47.         vector<int> line = {};
  48.         for (int j = 0; j < n; j++) {
  49.             int e;
  50.             cin >> e;
  51.             line.push_back(e);
  52.         }
  53.         table.push_back(line);
  54.     }
  55.     cout << find_gsum(table);
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement