Skip to content

Instantly share code, notes, and snippets.

@hamadu
Created January 3, 2017 10:26
Show Gist options
  • Save hamadu/cc6d87dbdab00b431b0be0c2924f7198 to your computer and use it in GitHub Desktop.
Save hamadu/cc6d87dbdab00b431b0be0c2924f7198 to your computer and use it in GitHub Desktop.
SRM691 Div1Medium : Moneymanager
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Moneymanager {
public int getbest(int[] a, int[] b, int X) {
List<int[]> w = new ArrayList<>();
int n = a.length;
for (int i = 0; i < n ; i++) {
w.add(new int[]{a[i], b[i]});
}
Collections.sort(w, (o1, o2) -> (o2[0] * o1[1]) - (o1[0] * o2[1]));
int bsum = w.stream().mapToInt(wi -> wi[1]).sum();
int best = 0;
for (int Y = n / 2 ; Y <= 10 * n / 2 ; Y++) {
int[][][] dp = new int[n+1][n/2+1][n*10+1];
for (int i = 0; i <= n ; i++) {
for (int j = 0; j <= n/2; j++) {
Arrays.fill(dp[i][j], -1);
}
}
dp[0][0][0] = 0;
int partSum = 0;
for (int i = 0; i < n ; i++) {
int A = w.get(i)[0];
int B = w.get(i)[1];
for (int c = 0; c <= n / 2 ; c++) {
for (int lb = 0; lb <= Y ; lb++) {
if (dp[i][c][lb] < 0) {
continue;
}
int base = dp[i][c][lb];
if (c < n / 2 && lb+B <= Y) {
dp[i+1][c+1][lb+B] = Math.max(dp[i+1][c+1][lb+B], base + (bsum - lb) * A);
}
int rb = partSum - lb;
dp[i+1][c][lb] = Math.max(dp[i+1][c][lb], base + (bsum - Y - rb) * A + X * B);
}
}
partSum += B;
}
best = Math.max(best, dp[n][n/2][Y]);
}
return best;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment