Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- const int INF = 1e8;
- using std::vector;
- using std::min;
- using std::max;
- int main() {
- int level, phones;
- std::cin >> level >> phones;
- vector<vector<int>> dp(level + 1, std::vector<int>(phones + 1));
- for (int lev = 1; lev <= level; ++lev) {
- dp[lev][1] = lev - 1;
- dp[lev][0] = INF;
- }
- for (int lev = 2; lev <= level; ++lev) {
- for (int phones_cnt = 2; phones_cnt <= phones; ++phones_cnt) {
- int best = INF;
- int left = 1;
- int right = lev - 1;
- while (left + 1 != right and left != right) {
- int middle = (left + right) >> 1;
- if (dp[lev - middle][phones_cnt] < dp[middle][phones_cnt-1]) {
- right = middle;
- }
- else {
- left = middle;
- }
- }
- best = min(max(dp[lev - right][phones_cnt], dp[right][phones_cnt-1]), max(dp[lev - left][phones_cnt], dp[left][phones_cnt-1]));
- dp[lev][phones_cnt] = 1 + best;
- }
- }
- if (dp[level][phones] == INF) {
- std::cout << -1;
- } else {
- if (phones >= log2(level)) {
- std::cout << ceil(log2(level));
- } else {
- std::cout << dp[level][phones];
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement