daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Jan 24th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <climits>
  3. using namespace std;
  4. ifstream cin("ciocolata.in");
  5. ofstream cout("ciocolata.out");
  6. long long matrix[500][500];
  7. int main()
  8. {
  9.     int n, m, upFinal, downFinal, leftFinal, rightFinal;
  10.     long long maxSum;
  11.     cin >> n >> m;
  12.     for (int i = 0; i < n; ++i)
  13.         for (int j = 0; j < m; ++j)
  14.             cin >> matrix[i][j];
  15.     maxSum = matrix[0][0];
  16.     for (int left = 0; left < m; ++left)
  17.     {
  18.         long long aux[n + 2];
  19.         for (int i = 0; i < n; ++i)
  20.             aux[i] = 0;
  21.         for (int right = left; right < m; ++right)
  22.         {
  23.             for (int i = 0; i < n; ++i)
  24.                 aux[i] += matrix[i][right];
  25.             long long maxSumK, sumK;
  26.             int st = 0, dr = 0, stFinal = 0, drFinal = 0;
  27.             maxSumK = sumK = aux[0];
  28.             for (int i = 1; i < n; ++i)
  29.             {
  30.                 if (aux[i] > aux[i] + sumK)
  31.                 {
  32.                     sumK = aux[i];
  33.                     st = dr = i;
  34.                 }
  35.                 else
  36.                 {
  37.                     ++dr;
  38.                     sumK+=aux[i];
  39.                 }
  40.                 if (sumK > maxSumK)
  41.                 {
  42.                     maxSumK = sumK;
  43.                     stFinal = st;
  44.                     drFinal = dr;
  45.                 }
  46.             }
  47.             if (maxSumK > maxSum)
  48.             {
  49.                 maxSum = maxSumK;
  50.                 upFinal = stFinal;
  51.                 downFinal = drFinal;
  52.                 leftFinal = left;
  53.                 rightFinal = right;
  54.             }
  55.         }
  56.     }
  57.     cout << maxSum << "\n";
  58.     cout << upFinal + 1 << " " << leftFinal + 1 << " " << upFinal + 1 << " " << rightFinal + 1 << "\n";
  59.     cout << downFinal + 1 << " " << leftFinal + 1 << " " << downFinal + 1 << " " << rightFinal + 1 << "\n";
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top