Submission #305400

#	Time	Username	Problem	Language	Result	Execution time	Memory
305400		llaki	Packing Biscuits (IOI20_biscuits)	Java	9 / 100	1510 ms	189236 KiB

biscuits

import java.util.ArrayList;

public class biscuits {
    long count_tastiness(long x, long[] a) {
        int k = a.length;
        long[] s = new long[k];
        s[0] = a[0];
        for (int i = 1; i < k; i++) {
            s[i] = (1l << i) * a[i] + s[i - 1];
        }
        ArrayList<Long> ys = new ArrayList<>();
        ys.add(0l);
        for (int i = 1; i < k; i++) {
            ArrayList<Long> newYs = new ArrayList<>();
            for (long y : ys) {
                newYs.add(y);
                long prev = eval(s, i - 1, x, y);
                if (prev > 0) {
                    newYs.add(y + (1l << (i - 1)));
                }
            }
            ys = newYs;
        }
        long ans = 0;
        for (long y : ys) {
            long eval = eval(s, k - 1, x, y);
            ans += eval + 1;
        }
        return ans;
        //return countRec(x, a, 0);
    }

    long eval(long[] s, int i, long x, long y) {
        // (s[i] - x * y) / (2^i * x);
        if (y >= s[i] / x) return 0;
        long up = s[i] - x * y;
        return (up / (1l << i)) / x;
    }

    long countRec(long x, long[] a, int index) {
        if (index == a.length - 1) {
            return a[a.length - 1] / x + 1;
        }
        long temp = a[index + 1];
        a[index + 1] = a[index + 1] + a[index] / 2;
        long answer = countRec(x, a, index + 1);
        if (a[index] >= x) {
            a[index + 1] = temp + (a[index] - x) / 2;
            answer += countRec(x, a, index + 1);
            a[index + 1] = temp;
        }
        a[index + 1] = temp;
        return answer;
    }

}
// (s[k-1] - i * X) / (2^(k-1)), 0 <= i < 2^(k - 1).
// For which i is this state valid?
// If for each position b s.t. b-th bit is set in i, (s[b+1] - (2^b + prev(i,b))X) / 2^(b+1) >= X.

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23