Submission #1106450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106450		snpmrnhlol	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	48 ms	1528 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
map <int,int> f;
int s[61];
int x2;
int solve(int nr){
    if(f.find(nr) != f.end())return f[nr];
    ///find answer
    int ans = 0;
    if(nr < 0)ans = 0;
    else if(nr == 0)ans = 1;
    else{
        int nr2 = 0;
        while((1LL<<(nr2 + 1)) <= nr)nr2++;
        //cout<<nr<<' '<<(1ll<<nr2) - 1<<'\n';
        ans+=solve((1ll<<nr2) - 1);
        ans+=solve(min(nr, s[nr2]/x2) - (1ll<<nr2));
    }
    f[nr] = ans;
    return f[nr];
}
long long count_tastiness(long long x, std::vector<long long> a) {
    f.clear();
    x2 = x;
    int k = 60;
    int sum = 0;
    a.resize(60);
    for(int i = 0;i < k - 1;i++){
        int nr = max(0ll,a[i] - x)/2*2;
        a[i]-=nr;
        a[i + 1]+=nr/2;
    }
    for(int i = 0;i < k;i++){
        sum+=(1ll<<i)*a[i];
        s[i] = sum;
    }
    return solve(sum/x);
}
/**
10
1 1
0
1 1
5
1 1
18
1 1
2664
1 1
97853
2 1
0 4663
3 1
0 0 1567
10 1
0 0 0 0 0 0 0 0 0 97
15 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
60 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
**/

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