Submission #469051

#	Time	Username	Problem	Language	Result	Execution time	Memory
469051		blue	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	110 ms	1316 KiB

biscuits

#include "biscuits.h"
#include <vector>
#include <iostream>
#include <map>
using namespace std;

//x = number of people (p)
//y = tastiness of each bag (i)

const int mx = 64;

long long pow2[mx];

long long* sm = new long long[1+mx] + 1;

map<long long, long long> CT;


long long X;
vector<long long> A;

int I(long long z)
{
    int I = 0;
    while(pow2[I+1] <= z) I++;
    return I;
}

long long Count(long long z)
{
    // cerr << "count " << z << '\n';
    if(z < 0) return 0;
    else if(z == 0) return 1;
    int i = I(z);

    if(CT.find(z) == CT.end())
    {
        CT[z] = Count(pow2[i] - 1) + Count(min(sm[i]/X - pow2[i], z - pow2[i]));
    }
    return CT[z];
 }

long long count_tastiness(long long x, vector<long long> a)
{
    while((int)a.size() < mx) a.push_back(0);

    CT.clear();

    pow2[0] = 1;
    for(int i = 1; i < mx; i++) pow2[i] = 2LL * pow2[i-1];
    sm[-1] = 0;
    for(int i = 0; i < mx; i++)
        sm[i] = sm[i-1] + pow2[i]*a[i];

    X = x;
    A = a;

    return Count(sm[mx-1]/x);
}

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