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!