Cod sursa(job #2574697)

Utilizator RagnoRazvan Petec Ragno Data 6 martie 2020 08:57:35
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define input "rufe.in", "rt", stdin
#define output "rufe.out", "wt", stdout
using namespace std;

typedef long long ll;

ll n, m, a, b, k;

ll calc(ll l, ll c, ll dist, bool cond)
{
    ll ans = 0;
    if (l + c <= dist) ans = (l + 1) * (c + 1);
         else
             ans = (dist + 1) * (dist + 2) / 2 -
                       (dist > l ? (dist - l) * (dist - l + 1) / 2 : 0) -
                       (dist > c ? (dist - c) * (dist - c + 1) / 2 : 0) ;

    if (cond == true) ans -= min(l, dist) + min (c, dist) + 1;
    return ans;
}

ll solve(ll dist)
{
    ll ans = calc(a - 1, b - 1, dist, 0) +
                 calc(n - a, m - b, dist, 0) +
                 calc(n - a, b - 1, dist, 1) +
                 calc(a - 1, m - b, dist, 1) - 1;
    return n * m - ans;
}

main()
{
    freopen(input);
    freopen(output);

    cin >> n >> m >> a >> b >> k;
    ll rez = 0, pas = (1LL << 60);

    while (pas)
    {
        if (rez + pas < n + m)
        {
            ll romb = solve(rez + pas);
            if (romb >= k) rez += pas;
        }
    pas /= 2;
    }
    cout << rez + 1;
    return 0;
}