Submission #1022194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022194		JakobZorz	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1095 ms	64012 KiB

biscuits

#include"biscuits.h"
#include<unordered_map>
typedef long long ll;
using namespace std;

ll x;
ll coins[120];
unordered_map<ll,ll>dp[120];

ll count(int i,ll num){
    if(i==120)
        return 1;
    if(dp[i].count(num))
        return dp[i][num];
    ll res=0;
    if(num>=x){
        res+=count(i+1,coins[i+1]+(num-x)/2);
    }
    res+=count(i+1,coins[i+1]+num/2);
    dp[i][num]=res;
    return res;
}

ll count_tastiness(ll X,vector<ll>a){
    x=X;
    for(int i=0;i<120;i++){
        coins[i]=0;
        dp[i].clear();
    }
    for(int i=0;i<(int)a.size();i++)
        coins[i]=a[i];
    
    for(int i=0;i<120;i++){
        ll num=(coins[i]-x)/2;
        if(num>0){
            coins[i+1]+=num;
            coins[i]-=2*num;
        }
    }
    
	return count(0,coins[0]);
}

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