oj.uz

Submission #305856

# Submission time Handle Problem Language Result Execution time Memory
305856 2020-09-24T03:09:01 Z llaki Packing Biscuits (IOI20_biscuits) Java 11
9 / 100
 1000 ms 11248 KB 
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);
    }

    long recursiveXIsOne(int pos, long first, long[] a) {
        if (pos == a.length - 1) {
            return first + 1;
        }
        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);
        }
        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 82 ms 10236 KB Output is correct
2 Correct 85 ms 10228 KB Output is correct
3 Correct 86 ms 10004 KB Output is correct
4 Correct 87 ms 10232 KB Output is correct
5 Correct 83 ms 10404 KB Output is correct
6 Correct 89 ms 10448 KB Output is correct
7 Correct 84 ms 10232 KB Output is correct
8 Correct 89 ms 10516 KB Output is correct
9 Correct 85 ms 10188 KB Output is correct
10 Correct 87 ms 10224 KB Output is correct
11 Correct 84 ms 10352 KB Output is correct
12 Correct 122 ms 10580 KB Output is correct
13 Correct 107 ms 10728 KB Output is correct
14 Correct 96 ms 10600 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10360 KB Output is correct
2 Execution timed out 1071 ms 10224 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 10332 KB Output is correct
2 Correct 86 ms 10224 KB Output is correct
3 Correct 87 ms 10092 KB Output is correct
4 Correct 174 ms 10768 KB Output is correct
5 Correct 179 ms 10724 KB Output is correct
6 Execution timed out 1016 ms 10520 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10600 KB Output is correct
2 Execution timed out 1031 ms 11248 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10236 KB Output is correct
2 Correct 85 ms 10228 KB Output is correct
3 Correct 86 ms 10004 KB Output is correct
4 Correct 87 ms 10232 KB Output is correct
5 Correct 83 ms 10404 KB Output is correct
6 Correct 89 ms 10448 KB Output is correct
7 Correct 84 ms 10232 KB Output is correct
8 Correct 89 ms 10516 KB Output is correct
9 Correct 85 ms 10188 KB Output is correct
10 Correct 87 ms 10224 KB Output is correct
11 Correct 84 ms 10352 KB Output is correct
12 Correct 122 ms 10580 KB Output is correct
13 Correct 107 ms 10728 KB Output is correct
14 Correct 96 ms 10600 KB Output is correct
15 Correct 87 ms 10360 KB Output is correct
16 Execution timed out 1071 ms 10224 KB Time limit exceeded
17 Halted 0 ms 0 KB -