sofwar
6/20/2018 - 5:51 PM

## solution

solution

``````<?php

function solution(int \$x, int \$y, int \$k, array \$a, array \$b): int
{
\$widths = length_calc(\$x, \$a);
\$heights = length_calc(\$y, \$b);

return size(\$widths, \$heights, \$k);
}

function length_calc(int \$length, array \$sections): array
{
\$data = [];

\$count_sections = \count(\$sections);

foreach (\$sections as \$section_id => \$section) {
\$data[] = \$section - (\$sections[\$section_id - 1] ?? 0);

if (\$count_sections === \$section_id + 1) {
\$data[] = \$length - (\$sections[\$section_id - 1] ?? 0);
}
}

sort(\$data, SORT_NUMERIC);

return \$data;
}

function size(array \$w, array \$h, int \$o): int
{
\$N = \count(\$w);

\$start = 1;
\$end = \$w[\$N - 1] * \$h[\$N - 1];

while (\$start <= \$end) {
\$middle = (\$start + \$end) >> 1;

\$cal = cal(\$middle, \$w, \$h);

if (\$cal >= \$o) {
\$start = \$middle + 1;
} else {
\$end = \$middle - 1;
}
}

return \$start;
}

function cal(int \$size, array \$w, array \$h): int
{
\$N = \count(\$w);

if (\$w[\$N - 1] * \$h[\$N - 1] <= \$size) {
return 0;
}

\$result = 0;
\$hIndex = \$N - 1;

foreach (range(0, \$N) as \$wIndex) {
while (\$hIndex >= 0 && \$w[\$wIndex] * \$h[\$hIndex] > \$size) {
\$hIndex -= 1;
}

\$result += \$N - 1 - \$hIndex;
}

return \$result;
}

\$x = 35;
\$y = 38;
\$k = 15;

\$a = [1, 3, 6, 11, 24, 26, 32];
\$b = [1, 5, 8, 13, 16, 22, 26];

echo solution(\$x, \$y, \$k, \$a, \$b);
``````