Submission #1272283

#TimeUsernameProblemLanguageResultExecution timeMemory
1272283neisennZemljište (COCI22_zemljiste)C++20
70 / 70
159 ms3400 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
const char nl = '\n';
const int mod = 1e9+7;
const int inf = 1e9;

void solve(){
    int n, m; cin >> n >> m;
    ll a, b; cin >> a >> b;
    int g[n+1][m+1];
    vector<vector<ll>> pref(n+1, vector<ll> (m+1, 0));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> g[i][j];
            pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+g[i][j];
        }
    }
    if (a > b) swap(a, b);
    ll ans = 1e18;
    for (int i = 1; i <= n; i++){
        for (int j = i; j <= n; j++){
            int l = 1, r = 1;
            ll val;
            while (l <= m and r <= m){
                if (l > r) r = l;
                val = pref[j][r]-pref[j][l-1]-pref[i-1][r]+pref[i-1][l-1];
                ans = min(ans, abs(a-val)+abs(b-val));
                if (val > b) l++;
                else r++;
            }
        }
    }
    cout << ans << nl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1; // cin >> t;
    while (t--){
        solve();
    }
    return 0;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...