Submission #729628

#	Time	Username	Problem	Language	Result	Execution time	Memory
729628		NemanjaSo2005	Packing Biscuits (IOI20_biscuits)	C++14	0 / 100	20 ms	10812 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MaxN=60;
ll N,K,res,kol[MaxN*4],stepen[MaxN*4],dp[MaxN+5][10010];
ll count_tastiness(ll k,vector<ll> A){
   stepen[0]=1;
   for(int i=1;i<=MaxN;i++)
      stepen[i]=stepen[i-1]*2;
   for(int i=MaxN+1;i<MaxN*4;i++)
      stepen[i]=1;
   K=k;
   res=1;
   N=A.size();
   for(int i=0;i<N;i++)
      kol[i]=A[i];
   for(int i=N;i<4*MaxN;i++)
      kol[i]=0;
   for(int i=0;i<4*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;*/
   int M=2*K+2;
   memset(dp,0,sizeof(dp));
   for(int i=0;i<=M;i++)
      if(i+K<=kol[0])
         dp[0][i]=2;
      else if(i<=kol[0])
         dp[0][i]=1;
      else
         dp[0][i]=0;
   for(int i=1;i<MaxN;i++){
      for(int j=0;j<=M;j++){
         ll r=0;
         /// Ne delis ga
         if(j<=kol[i])
            r+=dp[i-1][0];
         else
            if((j-kol[i]*2)<=M)
               r+=dp[i-1][(j-kol[i])*2]-dp[i-1][(j-kol[i])*2+1];
         /// Delis ga
         if(j+K<=kol[i])
            r+=dp[i-1][0];
         else if((j+K-kol[i])*2<=M)
            r+=dp[i-1][(j+K-kol[i])*2]-dp[i-1][(j+K-kol[i])*2+1];
         dp[i][j]=r;
      }
      //for(int j=M-1;j>=0;j--)
       //  dp[i][j]+=dp[i][j+1];
   }
   /*for(int j=M;j>=0;j--){
      for(int i=0;i<MaxN;i++)
         cout<<dp[i][j]<<" ";
      cout<<endl;
   }*/
   return dp[MaxN-1][0];
}

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