Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- using namespace std;
- vector<vector<int> > build_sum_table(vector<vector<int> > table) {
- vector<vector<int> > sum_table = {};
- for (int i = 0; i < table.size(); i++) {
- vector<int> sum_line = {0};
- for (int j = 0; j < table[0].size(); j++) {
- sum_line.push_back(sum_line[j] + table[i][j]);
- }
- sum_table.push_back(sum_line);
- }
- return sum_table;
- }
- int find_sum(vector<vector<int> > sum_table, int x1, int x2, int y) {
- return sum_table[y][x2 + 1] - sum_table[y][x1];
- }
- int find_gsum(vector<vector<int> > table) {
- vector<vector<int> > sum_table = build_sum_table(table);
- int gsum = table[0][0];
- for (int x2 = 0; x2 < table[0].size(); x2++) {
- for (int x1 = 0; x1 <= x2; x1++) {
- int imax = find_sum(sum_table, x1, x2, 0);
- for (int y = 1; y < table.size(); y++) {
- imax += find_sum(sum_table, x1, x2, y);
- if (find_sum(sum_table, x1, x2, y) > imax) {
- imax = find_sum(sum_table, x1, x2, y);
- }
- if (imax > gsum) {
- gsum = imax;
- }
- }
- }
- }
- return gsum;
- }
- int main() {
- int n;
- cin >> n;
- vector<vector<int> > table = {};
- for (int i = 0; i < n; i++) {
- vector<int> line = {};
- for (int j = 0; j < n; j++) {
- int e;
- cin >> e;
- line.push_back(e);
- }
- table.push_back(line);
- }
- cout << find_gsum(table);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement