This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
int n, m, a, b, i, j, x, l, r, mid;
ll mat[N][N], sm, tmp, ans;
ll f(int y){
return mat[x][y] - mat[x][j - 1] - mat[i - 1][y] + mat[i - 1][j - 1];
}
int main(){
cin >> n >> m >> a >> b;
for (i = 1; i <= n; i ++){
for (j = 1; j <= m; j ++){
cin >> mat[i][j];
mat[i][j] += mat[i - 1][j];
mat[i][j] += mat[i][j - 1];
mat[i][j] -= mat[i - 1][j - 1];
}
}
if (b < a) swap(a, b);
ans = 1e18;
for (i = 1; i <= n; i ++){
for (j = 1; j <= m; j ++){
for (x = i; x <= n; x ++){
sm = f(j);
tmp = abs(a - sm) + abs(b - sm);
ans = min(ans, tmp);
if (sm > b) break;
l = j;
r = m + 1;
while (r - l > 1){
mid = (l + r) / 2;
if (f(mid) > b)
r = mid;
else
l = mid;
}
sm = f(l);
ans = min(ans, abs(a - sm) + abs(b - sm));
if (l < m) sm = f(l + 1);
ans = min(ans, abs(a - sm) + abs(b - sm));
}
}
}
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |