# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
720592 | bin9638 | 비스킷 담기 (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
unordered_mapp<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