Submission #305952

#	Time	Username	Problem	Language	Result	Execution time	Memory
305952		llaki	Packing Biscuits (IOI20_biscuits)	Java	21 / 100	1089 ms	349532 KiB

biscuits

import java.util.*;

public class biscuits {
    long count_tastiness(long x, long[] a) {
        HashMap<Long, Long> freq = new HashMap<>();
        freq.put(a[0], 1l);
        long[] keys = new long[61 * 10001];
        long[] vals = new long[61 * 10001];
        for (int pos = 0; pos < a.length - 1; pos++) {
            int p = 0;
            for (Map.Entry<Long, Long> entry : freq.entrySet()) {
                keys[p] = entry.getKey();
                vals[p] = entry.getValue();
                p++;
            }
            freq.clear();
            for (int i = 0; i < p; i++) {
                long y = keys[i], value = vals[i];
                long val = a[pos + 1] + (y >> 1);
                freq.put(val, freq.getOrDefault(val, 0l) + value);
                if (y >= x) {
                    val = a[pos + 1] + ((y - x) >> 1);
                    freq.put(val, freq.getOrDefault(val, 0l) + value);
                }
            }
        }
        long ans = 0;
        for (long y : freq.keySet()) {
            ans += freq.get(y) * (y / x + 1);
        }
        return ans;
    }
}

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