
telephone call problem
Hello, could someone help me to solve the following problem?
A conversation time consists of N parts. Each of first N1 parts last for K[i] minutes, the Nth part is considered to be infinite. Each minute of a part i costs E[i]. Parts are consecutive, i.e. part N+1 always goes right after the end of part N. The pay is perminute (you pay at the beginning of a new minute for entire minute). If you have no enough money for a new minute, the conversation is interrupted.
You are given integers N and M. N1 integers K[i] and N integers E[i]. The task is to find the maximal possible number of minutes that you can speak over the telephone (it is possible to make several calls).
constraints:
1 <= N <= 77,
1 <= M, K[i], E[i] <= 1000000 (10^6)
time: 5 sec
memory: 64 mb
If you need a link to the problem to submit, it is here:
http://acm.lviv.ua/fusion/viewpage.p...=4b9bd89bef4d4