Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iomanip>
- #include <iostream>
- #include <vector>
- int main() {
- int amount;
- int capacity;
- std::cin >> amount >> capacity;
- std::vector<int> heights(amount + 1);
- for (int index = 0; index < amount - 1; ++index) {
- std::cin >> heights[index + 1];
- }
- heights[amount] = capacity + 1;
- std::vector<long double> r(amount + 1);
- int sp = 0;
- std::vector<int> ss(amount);
- std::vector<int> right(amount);
- for (int index = 0; index < amount + 1; ++index) {
- while (sp && heights[ss[sp - 1]] < heights[index]) {
- right[ss[--sp]] = index;
- }
- ss[sp++] = index;
- }
- int left_index = 0, index = 0;
- while (capacity > 0) {
- int right_index = right[index];
- if (static_cast<int64_t>(right_index - left_index) * heights[right_index] < capacity) {
- index = right_index;
- } else if (static_cast<int64_t>(right_index - left_index) * heights[index] < capacity) {
- auto h = static_cast<long double>(capacity) / (right_index - left_index);
- while (left_index < right_index) {
- r[left_index++] = h;
- }
- break;
- } else {
- while (left_index < index) {
- r[left_index++] = heights[index];
- capacity -= heights[index];
- }
- heights[index] = 0;
- right[index] = index + 1;
- }
- }
- std::cout << std::setprecision(7);
- for (int index = 0; index < amount; ++index) {
- std::cout << r[index] << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement