Dorsey Thief

                            Solution in C :

In C++ :





#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <climits>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <cmath>
#include <ctime>
#include <queue>
#include <list>
#include <map>
#include <set>

#define REP(i,n) for(int i = 0; i <(int)n; i++)
#define foreach(it,x) for(__typeof(x.begin()) it = x.begin() ;
   it!=x.end() ; it++ )

#ifdef KAZAR
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...)
#endif

using namespace std;

const int inf = (int)1e9 + 5757;

template<class T> inline void umax(T &a,T b){if(a<b) a = b;}
template<class T> inline void umin(T &a,T b){if(a>b) a = b;}
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}

inline int read(){int x;scanf(" %d",&x);return x;}

const int N = 5050;

long long dp[N];
vector<int> g[N];
vector<int> a,b;

int main(){

#ifdef KAZAR
    freopen("f.i","r",stdin);
    freopen("f.cik","w",stdout);
    freopen("error","w",stderr);
#endif

    int n = read();
    int x = read();

    for(int i = 1; i <= n; i++){
        int a = read(), v = read();
        if(v <= x){
            g[v].push_back(a);
        }
    }

    for(int i = 1; i <= x; i++){
        sort(g[i].begin(), g[i].end());
        reverse(g[i].begin(), g[i].end());
        int cnt = min(5000 / i + 1,(int)g[i].size());
        for(int j = 0; j < cnt; j++){
            a.push_back(i);
            b.push_back(g[i][j]);
        }
    }

    memset(dp, -1, sizeof dp);

    dp[0] = 0;

    eprintf("%d\n",a.size());

    for(int i = 0; i < (int)a.size(); i++){
        for(int j = x; j >= 0; j--)
            if(dp[j] != -1 && j + a[i] <= x)
                umax(dp[j + a[i]],dp[j] + b[i]);
    }

    if(dp[x] == -1){
        puts("Got caught!");
    }else{
        cout << dp[x] << endl;
    }

    return 0;
}








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());
	}
}








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;   
}