Submission #720583

#	Time	Username	Problem	Language	Result	Execution time	Memory
720583		bin9638	Packing Biscuits (IOI20_biscuits)	C++17	9 / 100	1073 ms	99336 KiB

biscuits

#include <bits/stdc++.h>

#ifndef SKY
#include "biscuits.h"
#endif // SKY

using namespace std;

#define N 110
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

const int num_bit=60;

int n;
vector<ll>a;
map<ll,ll>mp[N][N];
ll m;

ll get(ll sl,int pos,int cnt)
{
    if(cnt>=17)
        return 1;
    if(pos==num_bit)
        return 1;
    if(mp[pos][cnt].find(sl)!=mp[pos][cnt].end())
        return mp[pos][cnt][sl];
    ll res=get((sl+a[pos])/2,pos+1,cnt);
    if(sl+a[pos]>=m)
        res+=get((sl+a[pos]-m)/2,pos+1,cnt+1);
    return(mp[pos][cnt][sl]=res);
}

ll count_tastiness(ll cc, vector<ll> vec)
{
    n=vec.size();
    a=vec;
    m=cc;
    while(n<60)
        a.pb(0),n++;
    for(int i=0;i<=num_bit;i++)
        for(int j=0;j<=num_bit+1;j++)
            mp[i][j].clear();
    return get(0,0,0);
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    ll x,k;
    cin>>x>>k;
    vector<ll>a(k);
    for(int i=0;i<k;i++)
        cin>>a[i];
    cout<<count_tastiness(x,a);
    return 0;
}
#endif

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