Submission #932923

#TimeUsernameProblemLanguageResultExecution timeMemory
932923Amirreza_FakhriZemljište (COCI22_zemljiste)C++17
70 / 70
490 ms4956 KiB
// In the name of the God
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = (1e9+7)*(1e9+7);
const int mod = 998244353;
const int maxn = 5e2+5;

int r, s, a, b, c[maxn][maxn], ps[maxn][maxn];

int f1(int x1, int x2, int y1, int y2) {
    return ps[x2][y2]-ps[x1-1][y2]-ps[x2][y1-1]+ps[x1-1][y1-1];
}

int f2(int x) {
    return abs(x-a)+abs(x-b);
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> r >> s >> a >> b;
    if (a > b) swap(a, b);
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= s; j++) {
            cin >> c[i][j];
            ps[i][j] = ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+c[i][j];
        }
    }
    int ans = inf;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= r; j++) {
            int l = 1;
            for (int k = 1; k <= s; k++) {
                while (l < k and f1(i, j, l, k) > b) l++;
                smin(ans, f2(f1(i, j, l, k)));
                if (l-1) smin(ans, f2(f1(i, j, l-1, k)));
            }
        }
    }
    cout << ans << '\n';
    return 0;
} 











#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...