solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

template <class T>
auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D>
auto vect(const T& v, int n, D... m) {
    return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}

template <typename T>
static constexpr T inf = numeric_limits<T>::max() / 2;
mt19937_64 mrand(random_device{}());
long long rnd(long long x) { return mrand() % x; }
int lg2(long long x) { return sizeof(long long) * 8 - 1 - __builtin_clzll(x); }

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef pair<int, int> pii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


class Solution {
   public:
    int superEggDrop(int k, int n) {
        auto dp = vect(inf<int>, k + 1, n + 1);

        for (int i = 1; i <= n; i++) {
            dp[1][i] = i;
        }
        for (int i = 1; i <= k; i++) {
            dp[i][0] = 0;
        }

        auto work = [&](int x, int y) {
            int l = 1, r = y;
            int ans = l;
            while (l <= r) {
                int mid = l + r >> 1;
                if (dp[x - 1][mid - 1] <= dp[x][y - mid]) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            debug(x, y, ans);

            int tmp1 = 1 + dp[x][y - ans];
            if (ans + 1 <= y) {
                tmp1 = min(tmp1, 1 + dp[x - 1][ans]);
            }
            return tmp1;
        };     

        for (int i = 2; i <= k; i++) {
            dp[i][1] = 1;
            for (int j = 2; j <= n; j++) {
                int val = work(i, j);
                dp[i][j] = val;
                debug(i, j, dp[i][j]);
            }
        }
        return dp[k][n];
    }
};