HackerRank Dorsey Thief problem solution

In this HackerRank Dorsey Thief problem solution, Mr. Dorsey Dawson recently stole X grams of gold from ACME Jewellers. He is now on a train back home. To avoid getting caught by the police, he has to convert all the gold he has into paper money. He turns into a salesman and starts selling the gold on the train.

There are N passengers who have shown interest in buying the gold. The Ith passenger agrees to buy Ai grams of gold by paying Vi dollars. Dawson wants to escape from the police and also maximize the profit. Can you help him maximize the profit?

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;

    void solve() throws IOException {
        int n = nextInt();
        int x = nextInt();

        long[] max = new long[x + 1];
        Arrays.fill(max, -1);
        max[0] = 0;

        long freeBonus = 0;

        List<Integer>[] byNeed = new List[x + 1];
        for (int i = 1; i <= x; i++) {
            byNeed[i] = new ArrayList<>(0);
        }

        for (int i = 0; i < n; i++) {
            int gain = nextInt();
            int need = nextInt();
            if (need == 0) {
                freeBonus += gain;
                continue;
            }
            if (need <= x) {
                byNeed[need].add(gain);
            }

        }

        for (int need = 1; need <= x; need++) {
            List<Integer> cur = byNeed[need];
            Collections.sort(cur);
            Collections.reverse(cur);
            for (int i = 0; (i + 1) * need <= x && i < cur.size(); i++) {
                int gain = cur.get(i);
                for (int j = x; j >= need; j--) {
                    if (max[j - need] != -1) {
                        max[j] = Math.max(max[j], max[j - need] + gain);
                    }
                }
            }
        }

        if (max[x] == -1) {
            out.println("Got caught!");
        } else {
            out.println(max[x] + freeBonus);
        }
    }

    Solution() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Solution();
    }

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}

Problem solution in C++.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector<long long> profit(x + 1, -1);
    profit[0] = 0;
    for(int i = 0; i < n; ++i) {
        int price, amount;
        cin >> price >> amount;
        for(int pos = x; pos >= 0; --pos) {
            int newAmount = pos + amount;
            if(newAmount > x || profit[pos] == -1) {
                continue;
            }
            long long value = profit[pos] + price;
            profit[newAmount] = max(profit[newAmount], value);
        }
    }
    
    if(profit[x] == -1) {
        cout << "Got caught!" << endl;
    } else {
        cout << profit[x] << endl;
    }
             
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>

int main()
{ 
    int n,x;
    scanf("%d %d",&n,&x);
    int v[n],a[n];
    int temp=0;
    while(temp<n){
                  scanf("%d %d",&v[temp],&a[temp]);
                  temp++;
    }
    
    long long int dp[x+1];
    dp[0]=0;
    for(int i=1;i<=x;i++){
            dp[i]=-100000000000000000;
    }
    
    temp=0;
    while(temp<n){
                  for(int j=x;j>=a[temp];j--){
                          dp[j]=(dp[j]>dp[j-a[temp]]+v[temp])?dp[j]:(dp[j-a[temp]]+v[temp]);
                  }
                  temp++;
    }
    if(dp[x]>0){
                printf("%lld",dp[x]);
    }else{
          printf("Got caught!");
    }

return 0;   
}