Submission #396677

#	Time	Username	Problem	Language	Result	Execution time	Memory
396677		azberjibiou	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	69 ms	1332 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=62;
ll p[mxN];
ll xi[mxN];
ll pow2[mxN];
map <ll, ll> mp[mxN];
ll dping(int pos, ll val)
{
    if(mp[pos].find(val)!=mp[pos].end())    return mp[pos][val];
    if(pos==0)
    {
        return mp[pos][val]=val+1;
    }
    if(val<pow2[pos])   return mp[pos][val]=dping(pos-1, min(val, xi[pos-1]));
    return mp[pos][val]=dping(pos-1, min(val-pow2[pos], xi[pos-1]))+dping(pos-1, xi[pos-1]);
}
long long count_tastiness(long long x, std::vector<long long> a) {
    pow2[0]=1;
    for(int i=1;i<=60;i++)  pow2[i]=pow2[i-1]*2;
    int k=a.size();
    for(int i=0;i<60;i++)
    {
        if(i<k) p[i]=a[i];
        else    p[i]=0;
    }
    ll sum=0;
    for(int i=0;i<60;i++)
    {
        sum+=p[i]*pow2[i];
        xi[i]=min(pow2[i+1]-1, sum/x);
    }
    for(int i=0;i<60;i++)   mp[i].clear();
    return dping(59, xi[59]);
}

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