Submission #303730

#	Time	Username	Problem	Language	Result	Execution time	Memory
303730		denkendoemeer	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	191 ms	940 KiB

biscuits

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll>dp;
ll calc(ll num)
{
    ll u=0;
    while(num)
      {
      num=num/2;
      u++;
      }
    return u-1;
}
ll divide(ll x,vector<ll>a,ll lim)
{
    if (dp.find(lim)!=dp.end())
        return dp[lim];
    if (lim<=0)
        return 0;
    if (lim==1)
        return dp[lim]=1;
    ll nr=calc(lim-1);
    return dp[lim]=divide(x,a,1LL<<nr)+divide(x,a,min(lim,1+a[nr]/x)-(1LL<<nr));
}
ll count_tastiness(ll x,vector<ll>a)
{
    dp.clear();
    int i;
    for(i=1;i<a.size();i++)
        a[i]=a[i-1]+(a[i]<<i);
    while(a.size()<=64)
      a.push_back(a.back());
    return divide(x,a,1+a.back());
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(i=1;i<a.size();i++)
      |             ~^~~~~~~~~

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