NotImplemented's blog

By NotImplemented, 11 years ago, In Russian

Timus 1696

Посчитать число последовательностей длины N (N <= 1000) элементы которой из [1..K] (K <= 200) таких, что не существует i < j < k и A[i] > A[j] > A[k].

Очевидно, существует простое решение за N*K^3, если в состоянии запоминать два максимальных элемента, что, естественно, не проходит по времени.

Спасибо!

  • Vote: I like it
  • +5
  • Vote: I do not like it