Painter's Partition Problem

You have to paint N boards of length {A0, A1, A2, A3 AN-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint contiguous sections of board.

  • 2 painters cannot share a board to paint. That is to say, a board
    cannot be painted partially by one painter, and partially by another.
  • A painter will only paint contiguous boards. Which means a
    configuration where painter 1 paints board 1 and 3 but not 2 is
    invalid.

Return the ans % 10000003

Input :
K : Number of painters
T : Time taken by painter to paint 1 unit of board
L : A List which will represent length of each board

Output:
     return minimum time to paint all boards % 10000003

Example

Input : 
  K : 2
  T : 5
  L : [1, 10]
Output : 50
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Painter's Partition Problem on Interview Code Editor
Sign Up
to access hints and editorial solutions for Painter's Partition Problem
4092 successful submissions.
Asked In:
  • Google
Click here to start solving coding interview questions