Jedno z lepszych zadań jakie widziałem na wyszukiwanie binarne po wyniku. O(N^2 * log(max A_i)), gdzie max A_i to max wartosc w polu na planszy (i,j). Zauważamy, że zawsze wykonamy 2n-1 kroków w dojściu z pola (1,1) do (n,n). Szukamy binarnie, czy da się ułożyc o medianie x. Zauważmy, że musi być przynajmniej połowa (zaokrąglając w górę) elementów (w stosunku do całej drogi, która przebędziemy (2n-1)) >= x. Więc każdy element zamieniamy na 1, jak jest >= x, a na 0 jak jest mniejszy. I odpalamy klasycznego dynamika, z dojścia z (1,1) do (n,n) zbierając jak największą liczbę diamentów, jak w zadaniu tym:
https://szkopul.edu.pl/problemset/problem/8eq2zhM559QZjqVGNXFSv3st/site/?key=statement
lub tym:
https://sio2.mimuw.edu.pl/c/zwo20/p/dia/
I jak najlepsza droga > (2n-1) / 2, to zwaracamy w procedurze że się da, jak nie to zwracamy, że się nie da.