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