Submission #337326

#	Time	Username	Problem	Language	Result	Execution time	Memory
337326		mayflyyh	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	425 ms	1412 KiB

biscuits

#include <stdio.h>
#include <vector>
#include "biscuits.h"
using namespace std;
#define ll long long
ll dp[70];
ll count_tastiness(ll x, vector<ll> sz) {
    int k = sz.size();
    for (int i = 0; i < 62 - k; i++) sz.push_back(0);
    k = 62;
    for (int i = k; i >= 0; i--) {
        if (i == k) {
            dp[i] = 1;
            continue;
        }
        dp[i] = 0;
        for (int j = i + 1; j <= k; j++) {
            ll zx = 0, zd = (1ll << (j - i)) - 1, h = 0;
            for (int a = j - 1; a >= i; a--) {
                h = h * 2 + sz[a];
                ll z = (h / x + 1) << (a - i);
                if (a > i) {
                    if (z > zx)
                        zx = z;
                } else {
                    if (z - 1 < zd)
                        zd = z - 1;
                }
            }
            if (zx <= zd)
                dp[i] += dp[j] * (zd - zx + 1);
        }
    }
    return dp[0];
}

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