Advertisement
mfgnik

Untitled

Jul 14th, 2020
1,229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <iomanip>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5.  
  6. int main() {
  7.     int amount;
  8.     int capacity;
  9.     std::cin >> amount >> capacity;
  10.     std::vector<int> heights(amount + 1);
  11.     for (int index = 0; index < amount - 1; ++index) {
  12.         std::cin >> heights[index + 1];
  13.     }
  14.     heights[amount] = capacity + 1;
  15.     std::vector<long double> r(amount + 1);
  16.     int sp = 0;
  17.     std::vector<int> ss(amount);
  18.     std::vector<int> right(amount);
  19.     for (int index = 0; index < amount + 1; ++index) {
  20.         while (sp && heights[ss[sp - 1]] < heights[index]) {
  21.             right[ss[--sp]] = index;
  22.         }
  23.         ss[sp++] = index;
  24.     }
  25.  
  26.     int left_index = 0, index = 0;
  27.     while (capacity > 0) {
  28.         int right_index = right[index];
  29.         if (static_cast<int64_t>(right_index - left_index) * heights[right_index] < capacity) {
  30.             index = right_index;
  31.         } else if (static_cast<int64_t>(right_index - left_index) * heights[index] < capacity) {
  32.             auto h = static_cast<long double>(capacity) / (right_index - left_index);
  33.             while (left_index < right_index) {
  34.                 r[left_index++] = h;
  35.             }
  36.             break;
  37.         } else {
  38.             while (left_index < index) {
  39.                 r[left_index++] = heights[index];
  40.                 capacity -= heights[index];
  41.             }
  42.             heights[index] = 0;
  43.             right[index] = index + 1;
  44.         }
  45.     }
  46.     std::cout << std::setprecision(7);
  47.     for (int index = 0; index < amount; ++index) {
  48.         std::cout << r[index] << "\n";
  49.     }
  50.     return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement