Submission #729630

#	Time	Username	Problem	Language	Result	Execution time	Memory
729630		NemanjaSo2005	Packing Biscuits (IOI20_biscuits)	C++14	42 / 100	1073 ms	10580 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll koll[65],treba[65],tmp[65],X;
string A;
string ubin(int x){
   string ret="";
   while(x){
      if(x%2==1)
         ret.push_back(1);
      else
         ret.push_back(0);
      x/=2;
   }
   //reverse(ret.begin(),ret.end());
   return ret;
}
bool mozeli(int koji){
   A=ubin(koji);
   int N=A.size();
   for(int i=0;i<A.size();i++)
      treba[i+1]=A[i]*X;
   for(int i=1;i<=N;i++)
      tmp[i]=koll[i];
   for(int i=1;i<=N;i++){
      if(treba[i]>tmp[i])
         return false;
      tmp[i]-=treba[i];
      tmp[i+1]+=tmp[i]/2;
   }
   return true;
}
ll subtsk1(ll x,vector<ll> a){
   memset(koll,0,sizeof(koll));
   memset(treba,0,sizeof(treba));
   memset(tmp,0,sizeof(tmp));
   int K=a.size();
   X=x;
   for(int i=1;i<=K;i++)
      koll[i]=a[i-1];
   ll res=0;
   for(int i=0;i<=100000;i++){
      res+=mozeli(i);
   }
   return res;
}

#include "biscuits.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MaxN=60;
ll N,K,res,kol[MaxN+5],stepen[MaxN+5],dp[MaxN+5][20010],maxd[MaxN+5];
ll count_tastiness(ll k,vector<ll> A){
   if(k>10000)
      return subtsk1(k,A);
   stepen[0]=1;
   for(int i=1;i<=MaxN;i++)
      stepen[i]=stepen[i-1]*2;
   K=k;
   res=1;
   N=A.size();
   for(int i=0;i<N;i++)
      kol[i]=A[i];
   for(int i=N;i<=MaxN;i++)
      kol[i]=0;
   for(int i=0;i<=MaxN;i++)
      if(kol[i]>k+1){
         kol[i+1]+=(kol[i]-k)/2;
         kol[i]=k+(kol[i]-k)%2;
      }/*
   for(int i=0;i<=MaxN;i++)
      cout<<kol[i]<<" ";
   cout<<endl<<endl;*/
   maxd[0]=0;
   for(int i=1;i<=MaxN;i++)
      maxd[i]=(maxd[i-1]+kol[i-1])/2;
 /*  for(int i=0;i<=MaxN;i++)
      maxd[i]=10000;*/
   int M=2*K+2;
   memset(dp,0,sizeof(dp));
   for(int i=0;i<=maxd[MaxN];i++)
      if(kol[MaxN]+i<K)
         dp[MaxN][i]=1;
      else
         dp[MaxN][i]=2;
   for(int i=MaxN-1;i>=0;i--)
      for(int j=0;j<=maxd[i];j++){
         dp[i][j]=dp[i+1][(j+kol[i])/2];
         if(j+kol[i]>=K)
            dp[i][j]+=dp[i+1][(j+kol[i]-K)/2];
      }
   /*for(int j=M;j>=0;j--){
      for(int i=0;i<=MaxN;i++)
         cout<<dp[i][j]<<" ";
      cout<<endl;
   }*/
   return dp[0][0];
}

Compilation message (stderr)

biscuits.cpp: In function 'bool mozeli(int)':
biscuits.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |    for(int i=0;i<A.size();i++)
      |                ~^~~~~~~~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:81:8: warning: unused variable 'M' [-Wunused-variable]
   81 |    int M=2*K+2;
      |        ^

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