Submission #1090585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090585		TlenekWodoru	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	40 ms	1368 KiB

biscuits

#include<bits/stdc++.h>
#include "biscuits.h"
using namespace std;
bitset<128>tab[2][128];
bitset<128>B;
long long count_tastiness(long long x,vector<long long>AA)
{
    while(AA.size()<124){AA.push_back(0);}
    vector<__int128>A;
    for(auto u : AA){A.push_back(u);}
    const int n=A.size();
    __int128 s=0;
    vector<long long>dp(n);
    dp.push_back(1);
    for(int i=0;i<n;i++)
    {
        s+=A[i]*((long long)1<<i);
        __int128 u=s/x;
        if(u>=((__int128)1<<(i+1)))
        {
            for(int j=0;j<=i;j++)
            {
                tab[0][j][i]=0;
                tab[1][j][i]=1;
            }
        }
        else
        {
            for(int j=0;j<=i;j++)
            {
                if(u%2==0)
                {
                    tab[0][j][i]=1;
                    tab[1][j][i]=0;
                }
                else
                {
                    tab[0][j][i]=0;
                    tab[1][j][i]=1;
                }
                u>>=1;
            }
        }
    }
    for(int i=n-1;i>=0;i--)
    {
        if(dp[i+1]!=0)
        {
            for(int j=0;j<128;j++)
            {
                B[j]=0;
            }
            for(int j=i;j>=0;j--)
            {
                B[j]=1;
                if((B&tab[0][j]).count()==0)
                {
                    dp[j]+=dp[i+1];
                }
                else
                {
                    B&=tab[0][j];
                }
            }
            dp[0]+=dp[i+1];
        }
    }
	return dp[0];
}

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