Submission #413198

#	Time	Username	Problem	Language	Result	Execution time	Memory
413198		BJoozz	Packing Biscuits (IOI20_biscuits)	C++14	44 / 100	143 ms	892 KiB

biscuits

#include "biscuits.h"
#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
///shuffle(a.begin(), a.end(), rng)
#define int long long
const int MAX=63+4,inf=1e16,M2=5e5+3;
void maxx(int &a,int b){if(b>a) a=b;}
void minn(int &a,int b){if(b<a) a=b;}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}
bool cmax(int &a,int b){
    if(b>a){a=b;return 1;} else return 0;
}
typedef pair < int, int > ii;
void PL(int &a,int b){a+=b;}

int sum[63],lim[63];
bool B[63][63];
bool open[MAX];
int now[MAX];
int dp[MAX][MAX];
bool cmp(int u,int v){
    return now[u]>now[v];
}
long long count_tastiness(long long x, std::vector<long long> a) {
    memset(dp,0,sizeof dp);
    memset(now,0,sizeof now);
    while(a.size()<20) a.pb(0);
    int n=a.size();
    sum[0]=a[0];
    lim[0]=a[0]/x;
    lim[0]=min(lim[0],(1LL<<(0+1))-1);
    //for(int i=0;i<n;i++)bit[i]=1;
    for(int j=0;j<n;j++)B[0][j]=((lim[0]&(1LL<<j))!=0);
    for(int i=1;i<n;i++){
        sum[i]=sum[i-1]+(a[i]<<i);
        lim[i]=sum[i]/x;
        //if(lim[i]<(1LL<<i)){bit[i]=0;}
        lim[i]=min(lim[i],(1LL<<(i+1))-1);
        for(int j=0;j<n;j++)B[i][j]=((lim[i]&(1LL<<j))!=0);
    }

    vector < int > vec;
    for(int i=0;i<n;i++) vec.pb(i);
    dp[0][n]=1;
    //return 0;
    for(int i=0;i<n;i++){
        //cout<<sum[i]<<' '<<lim[i]<<'\n';
        //vec=V;
        //V.clear();
        memset(open,0,sizeof open);
        int sz=vec.size();
        //cout<<sz<<' '<<n<<'\n';
        for(int j=0;j<=sz;j++){

            if(dp[i][j]){
                ///(i)==0
                int num=0,dem=0;
                for(int k=i;k<n;k++)
                {
                    int z=open[k];
                    if(B[k][i])z=1;
                    num|=(z<<k);
                    dem+=z;
                }
                if(num&(1LL<<i)){
                    PL(dp[i+1][dem-1],dp[i][j]);
                }
            }
            if(dp[i][j]){
                ///(i)==1
                int num=0,dem=0;
                for(int k=i;k<n;k++)
                {
                    int z=open[k];
                    if(!B[k][i])z=0;
                    num|=(z<<k);
                    dem+=z;
                }
                if(num&(1LL<<i)){
                    PL(dp[i+1][dem-1],dp[i][j]);
                }
            }

            if(j<sz)open[vec[j]]=1;
        }
        vec.erase(find(vec.begin(),vec.end(),i));
        for(int j=0;j<n;j++)if(B[j][i]) now[j]|=(1LL<<i);
        sort(vec.begin(),vec.end(),cmp);
    }
    //cout<<dp[n][0]<<'\n';
	return dp[n][0];
}

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