Submission #413174

#TimeUsernameProblemLanguageResultExecution timeMemory
413174BJoozzPacking Biscuits (IOI20_biscuits)C++14
0 / 100
3 ms332 KiB
#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++) { bool 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++) { bool 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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...