Submission #1272076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272076		oswaldzz	Zemljište (COCI22_zemljiste)	C++20	70 / 70	1235 ms	4404 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl endl
#define hehe ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);  

const int mod = 1e9+7;
const int M = 2e5+5;

int g[505][505] = {};
int pf[505][505] = {};

int binser(const vector<int>& v, int x) {
    int l = 0, r = v.size();
    while (l < r){
        int mid = (l + r)/2;
        if (v[mid] < x) l = mid + 1;
        else r = mid;
    }
    return l;
}

void solve(){
    int n,m; cin >> n >> m;
    int a,b; cin >> a >> b;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            cin >> g[i][j];
        }
    }
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            pf[i][j] = g[i][j];
            if(i > 1) pf[i][j] += pf[i-1][j];
            if(j > 1) pf[i][j] += pf[i][j-1];
            if(i > 1 && j > 1) pf[i][j] -= pf[i-1][j-1];
        }
    }
    int l = min(a,b);
    int r = max(a,b);
    int ans = LLONG_MAX;
    int tmp = r-l;

    int sumcol[505];
    for(int i = 1; i <= n; i++){
        for(int k = 1; k <= m; k++) sumcol[k] = 0;
        for(int j = i; j <= n; j++){
            for(int k = 1; k<=m; k++) sumcol[k] += g[j][k];
            vector<int> pref;
            pref.push_back(0);
            int prefix = 0;
            for(int k = 1; k <= m; k++){
                prefix += sumcol[k];
                int low = prefix - r;
                int high = prefix - l;

                int idx = binser(pref, low);

                if(idx < pref.size() && pref[idx] <= high){
                    cout << tmp << nl;
                    return;
                }

                if(idx < pref.size()){
                    int s = prefix - pref[idx];
                    int dist = abs(s - a) + abs(s - b);
                    ans = min(dist, ans);
                }
                if(idx > 0){
                    int s = prefix - pref[idx-1];
                    int dist = abs(s - a) + abs(s - b);
                    ans = min(dist, ans);
                }

                int t = binser(pref, prefix);
                pref.insert(pref.begin() + t, prefix);
            }
        }
    }

    cout << ans << nl;
} 

signed main(){
    hehe
    int t = 1;
    while(t--){
        solve();
    }
}

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