SRM 528

Div2 - 250 MinCostPalindrome

public class MinCostPalindrome {
    public int getMinimum(String s, int oCost, int xCost) {
        int n = s.length();
        char a[] = s.toCharArray();
        int res = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (a[i] != '?' && a[n - i - 1] != '?') {
                if (a[i] != a[n - i - 1]) {
                    return -1;
                }
            } else {
                if (a[i] == '?' && a[n - i - 1] == '?') {
                    res += Math.min(oCost, xCost) * 2;
                } else if (a[i] == 'o' || a[n - i - 1] == 'o') {
                    res += oCost;
                } else {
                    res += xCost;
                }
            }
        }
        return res;
    }
}

Div2 - 500, Div1 - 250 Cut

import java.util.Arrays;
public class Cut {
    public int getMaximum(int[] lens, int cuts) {
        Arrays.sort(lens);
        int res = 0;
        for (int len : lens) {
            if (len % 10 != 0) continue;
            int need = len / 10 - 1;
            if (cuts >= need) {
                res += need + 1;
                cuts -= need;
            } else {
                res += cuts;
                cuts = 0;
            }
        }
        for (int len : lens) {
            if (len % 10 == 0 || len < 10) continue;
            int need = len / 10;
            if (cuts >= need) {
                res += need;
                cuts -= need;
            } else {
                res += cuts;
                cuts = 0;
            }
        }
        return res;
    }
}

Div2 - 1000 Mosquitoes

Div1 - 500 SPartition

Div1 - 1000 ColorfulCookie

public class ColorfulCookie {
    int[] cookies;
    int n, P1, P2;
    static final int MAX = 1000;
    int dp[][] = new int[MAX + 1][51];

    int rec(int n1, int k) {
        if (k == cookies.length) {
            if (n1 == 0) return 0;
            return Integer.MIN_VALUE;
        }
        if (dp[n1][k] != -1) return dp[n1][k];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i <= n1 && P1 * i <= cookies[k]; ++i) {
            int left = cookies[k] - P1 * i;
            int j = Math.min(left / P2, n - i);
            int t = rec(n1 - i, k + 1);
            if (t == Integer.MIN_VALUE) continue;
            res = Math.max(res, t + j);
        }
        return dp[n1][k] = res;
    }

    boolean check(int n) {
        this.n = n;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= cookies.length; ++j) {
                dp[i][j] = -1;
            }
        }
        return rec(n, 0) >= n;
    }
    public int getMaximum(int[] cookies, int P1, int P2) {
        this.cookies = cookies;
        this.P1 = P1;
        this.P2 = P2;
        int sum = 0;
        for (int cur : cookies) {
            sum += cur;
        }
        int lo = 0, hi = sum / (P1 + P2) + 1;
        hi = 1001;
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        return lo * (P1 + P2);
    }
}