# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
672761 | tbzard | Packing Biscuits (IOI20_biscuits) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long dp[210][10010];
long long count_tastiness(long long x, vector<long long> a){
memset(dp, 0, sizeof(dp));
vector<long long> b;
long long sum = 0;
for(int i=0;i<(int)a.size();i++){
sum += a[i];
if(sum > x) b.push_back(x), sum -= x;
else b.push_back(sum), sum = 0;
sum /= 2;
}
while(sum > 0){
if(sum > x) b.push_back(x), sum -= x;
sum /= 2;
}
dp[0][0] = 1;
for(int i=0;i<(int)b.size();i++){
for(int j=0;j<=10003;j++){
if(dp[i][j]){
dp[i+1][(j+b[i])/2] += dp[i][j];
if(j+b[i] >= x) dp[i+1][(j+b[i]-x)/2] += dp[i][j];
}
}
}
long long ans = 0;
for(int j=0;j<=10003;j++){
ans += dp[(int)b.size()][j];
}
return ans;
}
int main(){
long long n, x;
scanf("%lld%lld", &n, &x);
vector<long long> a(n);
for(int i=0;i<n;i++){
scanf("%lld", &a[i]);
}
printf("%lld\n", count_tastiness(n, a));
}