#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
long long L, R;
cin >> n >> m >> L >> R;
if (L > R) swap(L, R);
// min such >= l and <= r
// max <= l
// min >= r
vector<vector<long long>> a(n, vector<long long>(m));
for (auto &x : a) for (long long &i : x) cin >> i;
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] += a[i - 1][j];
}
}
auto get = [&](int i, int l, int r) {
return a[r][i] - (l ? a[l - 1][i] : 0LL);
};
const long long inf = 1e18;
long long y = -inf, z = inf;
{
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
long long sum = 0;
for (int l = 0, r = 0; r < m; r++) {
sum += get(r, i, j);
while (sum - get(l, i, j) >= L) {
sum -= get(l, i, j);
l++;
}
if (sum >= L && sum <= R) {
cout << R - L << '\n';
return 0;
}
}
}
}
}
{
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
long long sum = 0;
for (int l = 0, r = 0; r < m; r++) {
sum += get(r, i, j);
while (sum > L) {
sum -= get(l, i, j);
l++;
}
y = max(y, sum);
}
}
}
}
{
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
long long sum = 0;
for (int l = 0, r = 0; r < m; r++) {
sum += get(r, i, j);
while (sum - get(l, i, j) >= R) {
sum -= get(l, i, j);
l++;
}
if (sum >= R) z = min(z, sum);
}
}
}
}
if (y == 0) y = -inf;
cout << min(2 * z - L - R, L + R - 2 * y);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |