Advertisement
den4ik2003

Untitled

Feb 27th, 2022
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. const int INF = 1e8;
  6. using std::vector;
  7. using std::min;
  8. using std::max;
  9.  
  10. int main() {
  11.     int level, phones;
  12.     std::cin >> level >> phones;
  13.     vector<vector<int>> dp(level + 1, std::vector<int>(phones + 1));
  14.     for (int lev = 1; lev <= level; ++lev) {
  15.         dp[lev][1] = lev - 1;
  16.         dp[lev][0] = INF;
  17.     }
  18.  
  19.     for (int lev = 2; lev <= level; ++lev) {
  20.         for (int phones_cnt = 2; phones_cnt <= phones; ++phones_cnt) {
  21.             int best = INF;
  22.             int left = 1;
  23.             int right = lev - 1;
  24.             while (left + 1 != right and left != right) {
  25.                 int middle = (left + right) >> 1;
  26.                 if (dp[lev - middle][phones_cnt] < dp[middle][phones_cnt-1]) {
  27.                     right = middle;
  28.                 }
  29.                 else {
  30.                     left = middle;
  31.                 }
  32.             }
  33.             best = min(max(dp[lev - right][phones_cnt], dp[right][phones_cnt-1]), max(dp[lev - left][phones_cnt], dp[left][phones_cnt-1]));
  34.             dp[lev][phones_cnt] = 1 + best;
  35.         }
  36.     }
  37.  
  38.     if (dp[level][phones] == INF) {
  39.         std::cout << -1;
  40.     } else {
  41.         if (phones >= log2(level)) {
  42.             std::cout << ceil(log2(level));
  43.         } else {
  44.             std::cout << dp[level][phones];
  45.         }
  46.     }
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement