#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[62],lim[62];
bool bit[62];
bool B[62][62];
bool open[62];
int now[62];
int dp[62][62];
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);
int n=a.size();
sum[0]=a[0];
lim[0]=a[0]/x;
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++){
//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++)now[j]|=(B[j][i]<<i);
sort(vec.begin(),vec.end(),cmp);
}
//cout<<dp[n][0]<<'\n';
return dp[n][0];
}
Compilation message
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:49:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
49 | lim[i]=min(lim[i],(1LL<<i+1)-1);
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |