제출 #352396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
352396		G_X_J	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	39 ms	1388 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,b,a) for(int i=b;i>=a;--i)
#define ll long long
#define vi vector<ll>
using namespace std;
unordered_map <ll, ll> mp;
ll dp(ll n, ll x, const vi &s)
{
    if(n <= 0) return 0;
    if(n == 1) return 1;
    if(mp.find(n)!=mp.end()) return mp[n];
    ll power = 1ll << (__lg(n - 1));
    return mp[n] = dp(power, x, s) + dp(min(n, 1 + s[__lg(n - 1)] / x) - power, x, s);
}
ll count_tastiness(ll x, vi a)
{
    mp.clear();
    rep(i,1,(int)(a.size()) - 1) a[i] = a[i - 1] + (a[i] << i);//calculate s[i]
    while(a.size() <= 60) a.push_back(a.back());//a[i] is 0, so s[i] = s[i-1]
    return dp(1 + a.back(), x, a);
}//好jb短

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