Submission #776096

#	Time	Username	Problem	Language	Result	Execution time	Memory
776096		boris_mihov	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	118 ms	1384 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 (max > (1LL << bit + 1))
    {
        return f(bit - 1, max);
    }

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

    mem[{bit, max}] = f(bit - 1, std::min(max, (1LL << bit) - 1));
    mem[{bit, max}] += f(bit - 1, std::min(max, s[bit] / x) - (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 < MAXN ; ++i)
    {
        if (i < n)
        {
            a[i] = A[i];
            s[i] = a[i] * (1LL << i);
        } else
        {
            s[i] = 0;
        }

        if (i > 0) s[i] += s[i - 1];
    }

    mem.clear();
	return f(60, INF);
}

Compilation message (stderr)

biscuits.cpp: In function 'llong f(int, llong)':
biscuits.cpp:42:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   42 |     if (max > (1LL << bit + 1))
      |                       ~~~~^~~

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