255D - Mr Bender and Square - CodeForces Solution

#include <algorithm>
#include <iostream>

using namespace std;

long long count(int i, int j, int m) {
long long k = (long long) m * (m + 1) / 2;
if (m > i)
k -= (long long) (m - i) * (m - i + 1) / 2;
if (m > j)
k -= (long long) (m - j) * (m - j + 1) / 2;
if (m > i + j)
k += (long long) (m - i - j) * (m - i - j + 1) / 2;
return k;
}

int main() {
int n, i, j; long long k_; cin >> n >> i >> j >> k_;
int lower = -1, upper = n * 2;
while (upper - lower > 1) {
int m = (lower + upper) / 2;
if (count(i - 1, j - 1, m - 1) + count(i - 1, n - j, m - 1) + count(n - i, j - 1, m - 1) + count(n - i, n - j, m - 1) + min(m, i - 1) + min(m, j - 1) + min(m, n - i) + min(m, n - j) + 1 >= k_)
upper = m;
else
lower = m;
}
cout << upper << '\n';
return 0;
}