oj.uz

Submission #305857

# Submission time Handle Problem Language Result Execution time Memory
305857 2020-09-24T03:10:30 Z llaki Packing Biscuits (IOI20_biscuits) Java 11
9 / 100
 1000 ms 103616 KB 
import java.util.HashMap;

public class biscuits {
    long count_tastiness(long x, long[] a) {
        if (x == 1) {
            return solveXIsOne(a);
        }
        return countNaive(x, a);
    }

    // How many diff. sums can we get by  (n[i] * 2^i, where 0 <= n[i] <= a[i]).
    long solveXIsOne(long[] a) {
        return recursiveXIsOne(0, a[0], a);
    }

    HashMap<String, Long> map = new HashMap<>();

    String toKey(int pos, long first) {
        return pos + "." + first;
    }

    long recursiveXIsOne(int pos, long first, long[] a) {
        if (pos == a.length - 1) {
            return first + 1;
        }
        String key = toKey(pos, first);
        if (map.containsKey(key)) map.get(key);
        long res = recursiveXIsOne(pos + 1, a[pos + 1] + first / 2, a);
        if (first > 0) {
            res += recursiveXIsOne(pos + 1, a[pos + 1] + (first - 1) / 2, a);
        }
        map.put(key, res);
        return res;
    }

    long countNaive(long x, long[] a) {
        return countRec(x, a, 0);
    }

    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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 10620 KB Output is correct
2 Correct 89 ms 10236 KB Output is correct
3 Correct 85 ms 10340 KB Output is correct
4 Correct 86 ms 10344 KB Output is correct
5 Correct 84 ms 10400 KB Output is correct
6 Correct 103 ms 10600 KB Output is correct
7 Correct 85 ms 10360 KB Output is correct
8 Correct 108 ms 10936 KB Output is correct
9 Correct 91 ms 10132 KB Output is correct
10 Correct 86 ms 10252 KB Output is correct
11 Correct 86 ms 10228 KB Output is correct
12 Correct 123 ms 10760 KB Output is correct
13 Correct 111 ms 10744 KB Output is correct
14 Correct 98 ms 10728 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10488 KB Output is correct
2 Execution timed out 1032 ms 94468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10344 KB Output is correct
2 Correct 86 ms 10324 KB Output is correct
3 Correct 87 ms 10472 KB Output is correct
4 Execution timed out 1200 ms 103616 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 10744 KB Output is correct
2 Execution timed out 1105 ms 11384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 10620 KB Output is correct
2 Correct 89 ms 10236 KB Output is correct
3 Correct 85 ms 10340 KB Output is correct
4 Correct 86 ms 10344 KB Output is correct
5 Correct 84 ms 10400 KB Output is correct
6 Correct 103 ms 10600 KB Output is correct
7 Correct 85 ms 10360 KB Output is correct
8 Correct 108 ms 10936 KB Output is correct
9 Correct 91 ms 10132 KB Output is correct
10 Correct 86 ms 10252 KB Output is correct
11 Correct 86 ms 10228 KB Output is correct
12 Correct 123 ms 10760 KB Output is correct
13 Correct 111 ms 10744 KB Output is correct
14 Correct 98 ms 10728 KB Output is correct
15 Correct 91 ms 10488 KB Output is correct
16 Execution timed out 1032 ms 94468 KB Time limit exceeded
17 Halted 0 ms 0 KB -