[18111] 마인크래프트

https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

입력된 블럭들중 가장 작은것부터, 가장 큰것까지만 탐색하면 그안에 항상 최적해가 있음을 기대할 수 있다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

constexpr ll INF = INT_MAX;

ll n, m, b, sum, ansCost, ansHeight, a[501][501];

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m >> b;

    ll i, j, s = INF, e = 0;

    for (i = 0; i < n; i++) {

        for (j = 0; j < m; j++) {

            ll x;

            cin >> x;

            sum += x;

            s = min(x, s);

            e = max(x, e);

            a[i][j] = x;

        }

    }

    ansCost = INF;

    for (ll x = s; x <= e; x++) {

        if ((sum + b) < (x * n * m)) break;

        ll cost = 0, block = b;

        for (i = 0; i < n; i++) {

            for (j = 0; j < m; j++) {

                if (a[i][j] < x) {

                    ll cur = x - a[i][j];

                    cost += cur;

                    block -= cur;

                } else if (a[i][j] > x) {

                    ll cur = a[i][j] - x;

                    cost += (cur + cur);

                    block += cur;

                }

            }

        }

        if (block < 0) continue;

        if (cost <= ansCost) {

            ansCost = cost;

            ansHeight = x;

        }

    }

    cout << ansCost << ' ' << ansHeight;

    return 0;

}

---