Submission #1272183

#TimeUsernameProblemLanguageResultExecution timeMemory
1272183ttooppZemljište (COCI22_zemljiste)C++20
30 / 70
2094 ms6208 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int r, s, a, b, maxi;
ll arr[503][503], ans=1e18;
ll horizontal[503][503], vertikal[503][503];

ll count(ll x){
    return abs(a-x)+abs(b-x);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> r >> s >> a >> b;
    maxi=max(a, b);
    for(int i=1; i<=r; i++){
        for(int j=1; j<=s; j++){
            cin >> arr[i][j];
        }
    }

    for(int i=1; i<=r; i++){
        horizontal[i][0]=0;
        for(int j=1; j<=s; j++){
            horizontal[i][j]=horizontal[i][j-1]+arr[i][j];
        }
    }
    for(int j=1; j<=s; j++){
        vertikal[0][j]=0;
        for(int i=1; i<=r; i++){
            vertikal[i][j]=vertikal[i-1][j]+arr[i][j];
        }
    }
    for(int i=1; i<=r; i++){
        for(int j=1; j<=s; j++){
            for(int x=i; x<=r; x++){
                ll sum=0;
                for(int y=j; y<=s; y++){
                    sum+=vertikal[x][y]-vertikal[i-1][y];
                    //cout << sum <<endl;
                    ans=min(ans, count(sum));
                }
                sum=0;
            }
        }
    }
    cout << ans <<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...