Submission #776089

#	Time	Username	Problem	Language	Result	Execution time	Memory
776089		boris_mihov	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1 ms	340 KiB

biscuits

#include "biscuits.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>

typedef long long llong;
const int MAXN = 64;
const llong INF = 1e18;

struct Key
{
    int bit;
    llong max;

    friend bool operator < (const Key &a, const Key &b)
    {
        return a.bit < b.bit || (a.bit == b.bit && a.max < b.max);
    }
};

int n;
llong x;
llong a[MAXN];
llong s[MAXN];
std::map <Key, llong> mem;

llong f(int bit, llong max)
{
    if (max < 0)
    {
        return 0;
    }

    if (bit == -1)
    {
        return 1;
    }

    if (mem.count({bit, max}))
    {
        return mem[{bit, max}];
    }

    mem[{bit, max}] = f(bit - 1, std::min(max, s[bit]));
    mem[{bit, max}] += f(bit - 1, std::min(max, s[bit]) - (1LL << bit));
    return mem[{bit, max}];
}

llong count_tastiness(llong X, std::vector <llong> A)
{
    n = A.size();
    x = X;

    for (int i = 0 ; i < n ; ++i)
    {
        a[i] = A[i];
        s[i] = a[i] * (1LL << i);
        if (i > 0) s[i] += s[i - 1];
    }

    for (int i = 0 ; i < n ; ++i)
    {
        s[i] /= x;
    }

    mem.clear();
	return f(n - 1, INF);
}

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