made by Jaehyeok Choi

FAIL TO SOLVE ALONE

dynamic programming

Because time limit is 2 seconds, I though it can be solved with brute and force approach.

However, I failed to find the better solution, so I search for the internet.

The best solution's key is back-to-front approach. It means that fill the p array from day n.

To start with day 1 to n has lot of things to think. All cases (k=current calculating location, 1 day work + k day work, 2 day work + k day work,....... and find max)

But if I see from day n, there is no problem with the schedling because just comparing the (max value until current day) and (taking current day's work + max pay after taking current day's work) and find max.

If not taking the current day's work, then update the p[i] with p[i+1] will work. Only thing I have to check is that t[i] + i is bigger than the n.

To deal with that case, I make 17 length array(I'm going to start with the array index1) and fill the array with 0. If t[i] + i is bigger than n, just keep the eqaution p[i] = p[i+1] so that p[n] is over the due(n) fill it with 0.

The reason why I'm doing this is keep the situation that day in the middle is over due(n), the p array will be 0 and that makes error.

You can contact me through email, which is [email protected]. Thank you for visiting this github!