제출 #1150846

#제출 시각아이디문제언어결과실행 시간메모리
1150846DeathIsAweZemljište (COCI22_zemljiste)C++20
70 / 70
882 ms3384 KiB
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ll long long
ll prefix[501][501];
int grid[500][500];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a, b;
    int r, s; cin >> r >> s >> a >> b;
    if (a > b) swap(a, b);
    for (int i=0;i<r;i++) {
        for (int j=0;j<s;j++) {
            cin >> grid[i][j];
        }
    }


    for (int i=0;i<r;i++) {
        prefix[i][0] = 0;
    }
    for (int i=0;i<s;i++) {
        prefix[0][i] = 0;
    }
    for (int i=0;i<r;i++) {
        for (int j=0;j<s;j++) {
            prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
        }
    }


    ll ans = 1000000001;
    int bottom, top, middle;
    ll val1, val2;
    for (int i=0;i<r;i++) {
        for (int j=0;j<s;j++) {
            for (int k=j;k<s;k++) {
                bottom = i; top = r - 1;
                while (bottom + 1 < top) {
                    middle = (bottom + top) / 2;
                    if (prefix[middle + 1][k + 1] - prefix[middle + 1][j] - prefix[i][k + 1] + prefix[i][j] >= a) {
                        top = middle;
                    } else {
                        bottom = middle;
                    }
                }
                val1 = prefix[bottom + 1][k + 1] - prefix[bottom + 1][j] - prefix[i][k + 1] + prefix[i][j];
                val2 = prefix[top + 1][k + 1] - prefix[top + 1][j] - prefix[i][k + 1] + prefix[i][j];
                val1 = abs(a - val1) + abs(b - val1);
                val2 = abs(a - val2) + abs(b - val2);
                ans = min(ans, min(val1, val2));
            }
        }
        if (ans == abs(a - b)) {
            cout << ans; return 0;
        }
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...