E. Сайжруул!

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Манао дараах бодлогыг бодож байлаа:

Түүний бодолт зөв байсан боловч ажиллагаа нь хэтэрхий удаан байлаа. Танд түүний бодолтын хуурмаг-код өгөгджээ. (getAnswer функцын үр дүн нь бодлогын хариу)

getAnswer(a[1..n], b[1..len], h)
  answer = 0
  for i = 1 to n-len+1
    answer = answer + f(a[i..i+len-1], b, h, 1)
  return answer

f(s[1..len], b[1..len], h, index)
  if index = len+1 then
    return 1
  for i = 1 to len
    if s[index] + b[i] >= h
      mem = b[i]
      b[i] = 0
      res = f(s, b, h, index + 1)
      b[i] = mem
      if res > 0
        return 1
  return 0

Манаод алгоритмаа сайжруулахад нь тусална уу.

Оролт

Эхний мөрөнд $n$, $len$, $h$ ($1 ≤ len ≤ n ≤ 150000$; $1 ≤ h ≤ 10^9$) тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Хоёр дахь мөрөнд $len$ ширхэг зайгаар тусгаарлагдсан $b_1$, $b_2$, ..., $b_len$ ($1 ≤ b_i ≤ 10^9$) тоонууд.

Гурав дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан тоонууд $a_1$, $a_2$, ... , $a_n$ ($1 ≤ ai ≤ 10^9$) байрлана.

Гаралт

Хариу ганц тоо буюу Манаогийн програм ажиллаад гарсан хариу.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
5 2 10
5 3
1 8 5 5 7
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...