Misa-Misa's blog

Help Required On This Problem!
By Misa-Misa, history, 16 months ago, In English

Statement

You are given a vector of pairs (x_i, y_i) for size N.
Constraint : 1 <= x_i,y_i <=N and N<=1e5
For each j from 1 to N, find out the maximum value of j*x_i + y_i amongst all i's from 1 to N.

Finally print those N values.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Have a read of convex hull trick

→ Reply