Created
January 3, 2017 10:26
-
-
Save hamadu/cc6d87dbdab00b431b0be0c2924f7198 to your computer and use it in GitHub Desktop.
SRM691 Div1Medium : Moneymanager
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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