Vincent Massey SS - 2014 Senior Contest #1

Problem D: Pillaging

When Zihao isn't doing homework, he likes to go out with his gang and pillage some of the n (1 ≤ n ≤ 100,000) villages located along a river. Village i is located at some position p_i (1 ≤ p_i ≤ 1,000,000,000) along the river, and is either located on the left or the right side of the river. Furthermore, village i has a payout of x_i (0 ≤ x_i ≤ 10,000) dollars if Zihao decides to pillage it. He starts at position 0, on the left side of the river, with 0 dollars. His goal is to end up with as much money as possible at the end.

Unfortunately, Zihao is bound by the CCC (Canadian Constitution of Criminals) honour code. Firstly, he can only move from one village to another if the second village is located at a higher position along the river. Thus, he cannot move backwards. Secondly, Zihao can only pillage a city if he is on the same side of the river as the city. However, Zihao can cross the river in his boat at any point and as many times as he wants. Each time Zihao crosses the river, he must pay a tax of t (0 ≤ t ≤ 10,000) dollars. Zihao is allowed to have a negative amount of money at any point.

Input Format

The first line will contain two space-separated integers n and t.
The next n lines contain the information for each village in no particular order. Each of these lines will contain three space-separated integers, p_i, x_i, s_i, where s_i is 0 if the village is on the left side of the river and 1 if it is on the right side of the river.
No two villages will be at the same position.

Output Format

Print the largest possible amount of money Zihao can make by pillaging the villages with the restrictions stated above. You may assume that the answer will fit inside of a 32-bit integer.

Sample Input

4 10
1 10 0
4 15 0
2 17 1
3 10 1

Sample Output

32

Explanation

The optimal solution is to visit and pillage each city in order of position. You start on the left side of the river. First, pillage the village at position 1, giving you 10 dollars. Cross to the right side of the river (leaving you with 0 dollars) and pillage the village at position 2, giving you 17 dollars. Then pillage the village at position 3, giving you a total of 27 dollars. Cross back to the left side of the river (leaving you with 17 dollars) and pillage the village at position 4, giving you a grand total of 32 dollars.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 5.00s
Memory Limit: 16M
Added: Nov 04, 2014
Author: thorthugnasty

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

So, I've attempted a few different submissions but all seem to be caught on the same error. I've noticed something interesting with my code and I'm wondering if I could get a small recommendation or hint as to why it's doing this. This may or may not be the reason for the solution failing but I'm also just curious as to why this is happening.
Using this test case:

3 1
1 10 0
1 10 1
2 15 1

My code runs through the specific method I have set up, only to return later to continue the recursion with an index of -1, which I never set. I'm not too sure why it's happening.

Any assistance would be appreciated.

What if nextOnOther AND nextOnSame are -1?

EDIT: Ignore, as jargon pointed out, this won't occur, the base case will catch the situation where there is nothing left on either side

Not possible based on the premise of the recursive case.

Your problem is that you're using global variables. In your first iteration, you have nextOnOther = 2, nextOnSame = 1. This falls to your else case. Your recursion is dfs-like, so you'll go all the way down the other path. When you return from travel(nextOnOther), nextOnOther and nextOnSame will have been modified by later calls.

tl;dr use local vars thx

Thanks. Classic "don't use global variable" situation. Appreciate it.