Submission #720594

#	Time	Username	Problem	Language	Result	Execution time	Memory
720594		bin9638	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1066 ms	51276 KiB

biscuits

#include <bits/stdc++.h>

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

using namespace std;

#define N 1010
#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,dem;
vector<ll>a;
unordered_map<ll,ll>mp[N];
ll m,dp[N*N*10];

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

ll count_tastiness(ll cc, vector<ll> vec)
{
    n=vec.size();
    a=vec;
    m=cc;
    dem=0;
    while(n<60)
        a.pb(0),n++;
    for(int i=0;i<num_bit;i++)
        mp[i].clear();
    return get(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];
     //   a[i]=1ll*rand()*rand()%((ll)1e9/(i+1))+1;
    }
    cout<<count_tastiness(x,a);
    return 0;
}
#endif

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