unbelievable02's blog

IZHO 2009 problem.
By unbelievable02, history, 7 years ago, In English

Hello Codeforces!

I need help on IZHO 2009 E-problem. How to solve it?

Short description :

Given number n and two arrays, W[1...n], S[1...n].(n <= 1e5). And q queries. For each query given number k(k<=1e9), you must find pos, what d(pos, k) is maximum. Where d(x, k) = W[x] + k * S[x].

P.S sorry for my English.

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://wcipeg.com/wiki/Convex_hull_trick

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understand what we will use this, but how?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just add slopes like (S[x],W[x]). Then for every query you can find a answer with binary search or just sort the queries to use pointer technique.

      → Reply