oj.uz

Submission #413198

# Submission time Handle Problem Language Result Execution time Memory
413198 2021-05-28T11:04:23 Z BJoozz Packing Biscuits (IOI20_biscuits) C++14
44 / 100
 143 ms 892 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 108 ms 844 KB Output is correct
3 Correct 102 ms 848 KB Output is correct
4 Correct 124 ms 852 KB Output is correct
5 Correct 106 ms 852 KB Output is correct
6 Correct 139 ms 848 KB Output is correct
7 Correct 143 ms 844 KB Output is correct
8 Correct 129 ms 844 KB Output is correct
9 Correct 123 ms 844 KB Output is correct
10 Correct 107 ms 892 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -