Submission #1272393

#TimeUsernameProblemLanguageResultExecution timeMemory
1272393huhuhuhuhuZemljište (COCI22_zemljiste)C++20
0 / 70
1 ms568 KiB
#include <bits/stdc++.h>

using namespace std;

long long n, m, ab, ac;
long long grid[505][505];
long long psum[505][505];

long long getsum(long long a, long long l, long long r) {
  if (l == 0) {
    return psum[a][r];
  } else {
    return psum[a][r] - psum[a][l - 1];
  }
}

int main() {
  cin >> n >> m >> ab >> ac;
  for (int i = 0; i < n; i++) {
    long long sum = 0;
    for (int j = 0; j < m; j++) {
      cin >> grid[i][j];
      sum += grid[i][j];
      psum[i][j] = sum;
      // cout << psum[i][j] << " ";
    }
    // cout << endl;
  }

  long long mAns = 2e12;
  long long sx, sy, ex, ey;
  sx = sy = ex = ey = -1;

  for (int i = 0; i < m; i++) {
    for (int j = i; j < m; j++) {
      long long sum = 0;
      long long l = 0;
      long long r = -1;
      while (l < n && r < n) {
        if (r < l) {
          r = l - 1;
          sum = 0;
        }
        r++;
        if (r >= n || l >= n) {
          break;
        }
        sum += getsum(r, i, j);
        long long newAns = abs(sum - ab) + abs(sum - ac);
        long long lAns = mAns;
        // cout << sum << " " << psum[r][j] << " square [" << i << " " << l << "] [" << j << " " << r << "]" <<  endl;
        if (newAns < mAns) {
          sx = i; ex = j;
          sy = l; ey = r;
          mAns = newAns;
        }
        if (sum > max(ab, ac)) {
          // cout << "hi" << endl;
          sum -= getsum(l, i, j);
          l++;
        }
      }
    }
  }
  cout << mAns;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...