Submission #1272685

#TimeUsernameProblemLanguageResultExecution timeMemory
1272685ayhamzaiddZemljište (COCI22_zemljiste)C++20
70 / 70
243 ms4400 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define made '\n'

const ll N=505,MOD=1e9+7,INF=1e18;

ll pref[N][N],a[N][N];

ll f(int x,int y,int xx,int yy){
    ll cnt=pref[xx][yy];
    cnt-=pref[x-1][yy];
    cnt-=pref[xx][y-1];
    cnt+=pref[x-1][y-1];
    return cnt;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n,m,x,y;cin>>n>>m>>x>>y;
    if(x>y)swap(x,y);

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>a[i][j];
            pref[i][j]=pref[i][j-1]+a[i][j]+pref[i-1][j]-pref[i-1][j-1];
        }
    }
    ll mn=INF;
    for(int i=1; i<=n; i++){
        for(int k=i; k<=n; k++){
            for(int j=1,l=1; j<=m; j++){
                ll cnt=f(i,l,k,j);
                mn=min(mn,abs(x-cnt)+abs(y-cnt));
                while(cnt>y){
                    l++;
                    cnt=f(i,l,k,j);
                    mn=min(mn,abs(x-cnt)+abs(y-cnt)); 
                }
            }
        }
    }
    cout<<mn;
}

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