oj.uz

Submission #1036076

# Submission time Handle Problem Language Result Execution time Memory
1036076 2024-07-27T03:23:10 Z vjudge1 Zemljište (COCI22_zemljiste) C++17
0 / 70
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 505;
ll n, m, a, b, mat[N][N];

ll f(ll i, ll j, ll x, ll y){
    return mat[x][y] - mat[x][j - 1] - mat[i - 1][y] + mat[i - 1][j - 1];
}

int main(){
    cin >> n >> m >> a >> b;
    for (ll i = 1; i <= n; i ++){
        for (ll j = 1; j <= m; j ++){
            cin >> mat[i][j];

            mat[i][j] += mat[i - 1][j];
            mat[i][j] += mat[i][j - 1];
            mat[i][j] -= mat[i - 1][j - 1];
        }
    }

    ll ans = 1e18;
    for (ll i = 1; i <= n; i ++){
        for (ll j = 1; j <= m; j ++){
            for (ll x = i; x <= n; x ++){
                if (f(i, j, x, j) > b) break;
                
                ll l = j;
                ll r = m + 1;
                while (r - l > 1){
                    ll mid = (l + r) / 2;
                    if (f(i, j, x, mid) > b)
                        r = mid;
                    else
                        l = mid;
                }

                ll sm = f(i, j, x, l);
                ans = min(ans, abs(a - sm) + abs(b - sm));

                if (l < m) sm = f(i, j, x, l + 1);
                ans = min(ans, abs(a - sm) + abs(b - sm));
            }
        }
    }

    cout << ans << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -