[BOJ] 17245 서버실

#include <iostream>
#include <vector>
#include <algorithm>
#define ull unsigned long long
using namespace std;

const int MAX_N = 1001;
int n;
int map[MAX_N][MAX_N];

ull calculateSumAndMaxValue(ull& maxValue) {
    ull sum = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> map[i][j];
            sum += map[i][j];
            maxValue = max(maxValue, static_cast<ull>(map[i][j]));
        }
    }
    return sum;
}

bool isValidMid(ull mid, ull sum) {
    ull cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cnt += min(mid, static_cast<ull>(map[i][j]));
        }
    }
    return (static_cast<double>(cnt) / sum) >= 0.5;
}

ull findOptimalValue(ull sum, ull maxValue) {
    ull left = 0, right = maxValue;
    while (left + 1 < right) {
        ull mid = (left + right) / 2;
        if (isValidMid(mid, sum))
            right = mid;
        else
            left = mid;
    }
    return right;
}

int main() {
    cin >> n;
    ull maxValue = 0;
    ull sum = calculateSumAndMaxValue(maxValue);
    ull result = findOptimalValue(sum, maxValue);
    
    cout << result << endl;
    
    return 0;
}