Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector< vector<int> > d; //массив для динамики
- int get_sum(int x1, int x2, int y1, int y2)
- {
- if (x1 == 1 && y1 == 1) {
- return d[x2][y2];
- } else if (x1 == 1) {
- return d[x2][y2] - d[x2][y1 - 1];
- } else if (y1 == 1) {
- return d[x2][y2] - d[x1 - 1][y2];
- } else {
- return d[x2][y2] - d[x2][y1 - 1] - d[x1 - 1][y2] + d[x1 - 1][y1 - 1];
- }
- }
- int main()
- {
- int n;
- cin >> n;
- vector< vector<int> > a(n, vector<int> (n)); //данная матрица
- d.resize(n + 1, vector<int> (n + 1));
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j)
- cin >> a[i][j];
- }
- for (int i = 1; i < n + 1; ++i) {
- d[i][1] = a[i - 1][0] + d[i - 1][1];
- d[1][i] = a[0][i - 1] + d[1][i - 1];
- }
- for (int i = 2; i < n + 1; ++i) {
- for (int j = 2; j < n + 1; ++j) {
- d[i][j] = d[i - 1][j] + d[i][j - 1] + a[i - 1][j - 1] - d[i - 1][j - 1];
- }
- }
- int max_sum = -1e9;
- for (int x1 = 1; x1 < n + 1; ++x1) {
- for (int x2 = x1; x2 < n + 1; ++x2) {
- for (int y1 = 1; y1 < n + 1; ++y1) {
- for (int y2 = y1; y2 < n + 1; ++y2) {
- max_sum = max(max_sum, get_sum(x1, x2, y1, y2));
- }
- }
- }
- }
- cout << max_sum << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment