Submission #354418

#	Time	Username	Problem	Language	Result	Execution time	Memory
354418		Osama_Alkhodairy	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1097 ms	41868 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

int k;
ll x;
unordered_map <ll, ll> dp[61];
vector <ll> a;

ll solve(int idx, int p){
    if(idx == k) return 1;
    if(dp[idx].find(p) != dp[idx].end()) return dp[idx][p];
    ll &ret = dp[idx][p];
    ret = 0;
    ll f = a[idx] + p;
    ret += solve(idx + 1, f / 2);
    if(f >= x){
        ret += solve(idx + 1, (f - x) / 2);
    }
    return ret;
}
long long count_tastiness(long long X, vector<long long> A){
    x = X;
    a = A;
    k = a.size();
    while(k < 60){
        a.push_back(0);
        k++;
    }
    for(int i = 0 ; i < 61 ; i++){
        dp[i].clear();
    }
    for(int i = 0 ; i < k ; i++){
        if(a[i] <= x) continue;
        ll f = a[i] - x;
        f -= f % 2;
        a[i] -= f;
        if(i + 1 < k) a[i + 1] += f / 2;
    }
    return solve(0, 0);
}

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