Submission #400768

#TimeUsernameProblemLanguageResultExecution timeMemory
400768REALITYNBPacking Biscuits (IOI20_biscuits)C++17
0 / 100
1080 ms332 KiB
#include <bits/stdc++.h> #include "biscuits.h" #define int long long using namespace std; int sub1(int k , vector<int> a){ int ans = 0 ; int n = 60 ; while(a.size()!=n+1) a.push_back(0) ; for(int target=0;target<=100000;target++){ vector<int>b=a; bool flg =1 ; for(int i=0;i<n;i++){ if((1<<i)&target){ if(b[i]<k){ flg=0 ; break ; } b[i]-=k; b[i+1]+=b[i]/2 ; } else b[i+1]+=b[i]/2 ; } ans+=flg; } return ans ; } int count_tastiness(int k,vector<int> a){ if(k!=1) return sub1(k,a) ; int n =120 ; while(n!=a.size()) a.push_back(0) ; vector<int> dp(n+1); dp[n]=1; for(int i=n-1;i>-1;i--){ int sum = 0 ; vector<int> b=a; int stop = i+1; for(int j=i;j<n;j++){ if(b[j]>1){ b[j+1]+=b[j]/2; if(b[j]&1) b[j]=1; else b[j]=0; stop=j+2; } else break ; } if(a[i]==0) { dp[i]+=dp[i+1] ; continue ; } vector<int> in ; for(int j=i;j<stop;j++) if(b[j]) in.push_back(j) ; for(int j=1;j<in.size();j++) dp[i]+=dp[stop]*(1LL<<(in[j-1]-i)); dp[i]+=dp[stop]; dp[i]+=dp[stop]*(1<<(in.back()-i)) ; } return dp[0] ; }

Compilation message (stderr)

biscuits.cpp: In function 'long long int sub1(long long int, std::vector<long long int>)':
biscuits.cpp:8:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
    8 |     while(a.size()!=n+1) a.push_back(0) ;
      |           ~~~~~~~~^~~~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:32:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while(n!=a.size()) a.push_back(0) ;
      |           ~^~~~~~~~~~
biscuits.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=1;j<in.size();j++)
      |                     ~^~~~~~~~~~
biscuits.cpp:36:13: warning: unused variable 'sum' [-Wunused-variable]
   36 |         int sum = 0 ;
      |             ^~~
#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...