Submission #1272230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272230		choed	Zemljište (COCI22_zemljiste)	C++20	70 / 70	173 ms	4364 KiB

Main

#include <bits/stdc++.h>
#define GO_BEYOND ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
using namespace std;

void solve(){
    ll n, m; cin >> n >> m;
    ll a, b; cin >> a >> b;
    if(a>b) swap(a,b);

    ll grid[n+1][m+1];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++)
            cin >> grid[i][j];
    }

    ll pfs[n+1][m+1], add, sub;
    memset(pfs,0,sizeof(pfs));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            add=pfs[i][j-1]+pfs[i-1][j];
            sub=pfs[i-1][j-1];
            pfs[i][j]=add-sub+grid[i][j];
        }
    }

    ll ans=LLONG_MAX, lp, rp, cur;
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            lp=rp=1;
            while(rp<=m && lp<=m){
                if(lp>rp) rp=lp;
                add=pfs[j][rp]+pfs[i-1][lp-1];
                sub=pfs[j][lp-1]+pfs[i-1][rp];
                cur=add-sub;

                // cout << i << ' ' << j << endl;
                // cout << lp << ' ' << rp << endl;
                // cout << cur << endl; 
                ans=min(ans, abs(a-cur)+abs(b-cur));
                if(cur>b) lp++;
                else rp++;
            }
        }
    }
    cout << ans << endl;
}

/*
g++ sigma.cpp -o a
2 2 10 10
1 3
4 1

3 2 3 4
1 9
1 1
8 1

3 4 5 3
1 1 1 1
9 6 7 6
8 1 9 7
*/

int main(){
    GO_BEYOND;
    ll t=1;
    // cin >> t;
    while(t--) 
        solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40