memoize.cc

#include <bits/stdc++.h>
using namespace std;

template<typename Res, typename ...Args> struct _memoized{//{{{
    function<Res(Args...)> f;
    map<tuple<Args...>, Res> memo;
    _memoized(function<Res(Args...)> &f) : f(f){}

    Res operator()(Args ...args){
        const auto &key = make_tuple(args...);
        if(memo.count(key)) return memo[key];
        return memo[key] = f(args...);
    }
};//}}}
template<typename Res, typename ...Args>
function<Res(Args...)> memoize(function<Res(Args...)> &f){ f = _memoized<Res, Args...>(f); return f; }

bool solve(){
    function<int(int)> f = [&](int n) -> int{ return n <= 1 ? n : f(n-1) + f(n-2); };
    memoize(f);
    cout << f(100) << endl;
    return true;
}
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s: