Indian Computing Olympiad

Training Material


A shoemaker has N jobs (orders from customers) to execute.

  • The shoemaker can work on only one job each day.
  • For each job i, T[i] (1≤T[i]≤1000) is the time in days it takes the shoemaker to finish the job.
  • For each day of delay before starting to work on job i, the shoemaker must pay a fine of S[i] cents (1≤S[i]≤10000).

Your task is to help the shoemaker to find the sequence of jobs with minimal total fine.