Submission #1272110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272110		rana_azka	Zemljište (COCI22_zemljiste)	C++20	0 / 70	0 ms	332 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 500;

int n, m;
int a, b;
int arr[MAXN+5][MAXN+5];

void mulaidarinol(){}

void solve(){
    cin >> n >> m >> a >> b;
    if(a > b) swap(a, b);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> arr[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
        }
    }    
    
    int ans = INF;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = i; k <= n; k++){
                int idx = j;
                int left = j, right = m;
                int mid;
                while(left <= right){
                    mid = (left + right) / 2;

                    int temp = arr[k][mid] - arr[k][j-1] - arr[i-1][mid] + arr[i-1][j+1];
                    if(temp <= a){
                        idx = mid;
                        left = mid + 1;
                    }else{
                        right = mid - 1;
                    }
                }

                // cerr << i << ' ' << j << " : " << k << ' ' << idx << endl;

                int temp = arr[k][idx] - arr[k][j-1] - arr[i-1][idx] + arr[i-1][j+1];
                ans = min(abs(a - temp) + abs(b - temp), ans);

                if(idx > j){
                    temp = arr[k][idx-1] - arr[k][j-1] - arr[i-1][idx-1] + arr[i-1][j+1];
                    ans = min(abs(a - temp) + abs(b - temp), ans);
                }

                if(idx < m){
                    temp = arr[k][idx+1] - arr[k][j-1] - arr[i-1][idx+1] + arr[i-1][j+1];
                    ans = min(abs(a - temp) + abs(b - temp), ans);
                }
            }
        }
    }

    cout << ans << endl;
}

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

    int tc = 1;
    // cin >> tc;
    while(tc--){
        // mulaidarinol();
        solve();
        // cerr << endl;
    }

    return 0;
}

/*
TEST CASE

2 2 10 10 
1 3
4 1
=> 2

3 2 3 4
1 9
1 1
8 1
=> 3

3 4 5 3
1 1 1 1
9 6 7 6
8 1 9 7
=> 2
*/

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