Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <climits>
- using namespace std;
- ifstream cin("ciocolata.in");
- ofstream cout("ciocolata.out");
- long long matrix[500][500];
- int main()
- {
- int n, m, upFinal, downFinal, leftFinal, rightFinal;
- long long maxSum;
- cin >> n >> m;
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < m; ++j)
- cin >> matrix[i][j];
- maxSum = matrix[0][0];
- for (int left = 0; left < m; ++left)
- {
- long long aux[n + 2];
- for (int i = 0; i < n; ++i)
- aux[i] = 0;
- for (int right = left; right < m; ++right)
- {
- for (int i = 0; i < n; ++i)
- aux[i] += matrix[i][right];
- long long maxSumK, sumK;
- int st = 0, dr = 0, stFinal = 0, drFinal = 0;
- maxSumK = sumK = aux[0];
- for (int i = 1; i < n; ++i)
- {
- if (aux[i] > aux[i] + sumK)
- {
- sumK = aux[i];
- st = dr = i;
- }
- else
- {
- ++dr;
- sumK+=aux[i];
- }
- if (sumK > maxSumK)
- {
- maxSumK = sumK;
- stFinal = st;
- drFinal = dr;
- }
- }
- if (maxSumK > maxSum)
- {
- maxSum = maxSumK;
- upFinal = stFinal;
- downFinal = drFinal;
- leftFinal = left;
- rightFinal = right;
- }
- }
- }
- cout << maxSum << "\n";
- cout << upFinal + 1 << " " << leftFinal + 1 << " " << upFinal + 1 << " " << rightFinal + 1 << "\n";
- cout << downFinal + 1 << " " << leftFinal + 1 << " " << downFinal + 1 << " " << rightFinal + 1 << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement