Hello,

I tried to solve an interesting div1 500 problem from SRM 352 (of TopCoder). Here is the link of problem: https://community.topcoder.com/stat?c=problem_statement&pm=7481&rd=10709&rm=264976&cr=264869

After reading the solutions, I decided to re-implement an easy, yet clever solution by bmerry. The solution is written in C++. It is fast and can pass the system tests by taking at most 0.5 milliseconds. I wrote a very similar solution in Java:

public class FibonacciKnapsack {
	Long[][] items;
	long[] weightSum;
	long[] priceSum;
	long bruteforce(int idx, long C, int usedLast) {
		if(idx == items.length)
			return 0;
		if(weightSum[idx] <= C)
			return priceSum[idx];
		else if(items[idx][0] <= C && (usedLast == 1 || items[idx][0] != items[idx - 1][0])) {
			long a = bruteforce(idx + 1, C - items[idx][0], 1) + items[idx][1];
			long b = bruteforce(idx + 1, C, 0);
			return Math.max(a, b);
		} else {
			long a = bruteforce(idx + 1, C, 0);
			return a;
		}
	}
	public long maximalCost(String[] itemsString, String _C) {
		long C = Long.parseLong(_C);
		int n = itemsString.length;
		items = new Long[n][2];
		for(int i = 0; i < n; i ++) {
			StringTokenizer st = new StringTokenizer(itemsString[i]);
			items[i][0] = Long.parseLong(st.nextToken());
			items[i][1] = Long.parseLong(st.nextToken());
		}
		Arrays.sort(items, new Comparator<Long[]>() {
			@Override
			public int compare(Long[] o1, Long[] o2) {
				if(o1[0] != o2[0]) return o1[0] > o2[0]? -1: 1;
				return o1[1] > o2[1]? -1: 1;
			}
		});
		weightSum = new long[n];
		priceSum = new long[n];
		for(int i = 0; i < n; i ++) {
			for(int j = i; j < n; j ++) {
				weightSum[i] += items[j][0];
				priceSum[i] += items[j][1];
			}
		}
		long ans = bruteforce(0, C, 1);
		return ans;
	}
}

I expected to get a similar performance. However, it turns out to be so slow on the following test case (taking more than 5 seconds on my machine):

String[] items = {"196418 196418", "196418 196419", "317811 317811", "317811 317812", "514229 514229", "514229 514230", "832040 832040", "832040 832041", "1346269 1346269", "1346269 1346270", "2178309 2178309", "2178309 2178310", "3524578 3524578", "3524578 3524579", "5702887 5702887", "5702887 5702888", "9227465 9227465", "9227465 9227466", "14930352 14930352", "14930352 14930353", "24157817 24157817", "24157817 24157818", "39088169 39088169", "39088169 39088170", "63245986 63245986", "63245986 63245987", "102334155 102334155", "102334155 102334156", "165580141 165580141", "165580141 165580142", "267914296 267914296", "267914296 267914297", "433494437 433494437", "433494437 433494438", "701408733 701408733", "701408733 701408734", "1134903170 1134903170", "1134903170 1134903171", "1836311903 1836311903", "1836311903 1836311904", "2971215073 2971215073", "2971215073 2971215074", "4807526976 4807526976", "4807526976 4807526977", "7778742049 7778742049", "7778742049 7778742050", "12586269025 12586269025", "12586269025 12586269026", "20365011074 20365011074", "20365011074 20365011075"};
String C = "65902560198";
expected_answer = 65902560223L;

I am wondering what makes the Java code so slow. Also, it would be good to know if there is any way/trick to make it as fast as the C++ implementation.