#include #include #include class POND{ public: double volume; int rate; bool full; double remains; int array_index; int heap_index; POND* next; POND* prev; void adjust_volume(double delta_time){ volume -= rate*delta_time; remains = volume/rate; } void add_rate(int new_rate){ rate += new_rate; remains = volume/rate; } }; class heap_elem{ public: POND* pond; }; bool operator<(const heap_elem& lhs, const heap_elem& rhs){ return ((lhs.pond)->remains > (rhs.pond)->remains); } POND ponds[100001]; int main() { int N, F; while(scanf("%d %d", &N, &F) != EOF){ std::vector heap; heap.reserve(N); for(int i = 0; i < N; i++){ scanf("%lf", &(ponds[i].volume)); ponds[i].full = false; ponds[i].rate = F; ponds[i].remains = ((double)ponds[i].volume)/((double)F); ponds[i].array_index = i; if (i + 1 < N){ ponds[i].next = &(ponds[i+1]);} else {ponds[i].next = NULL;} if (i - 1 >= 0) {ponds[i].prev = &(ponds[i-1]);} else {ponds[i].prev = NULL;} heap_elem elem; elem.pond = &(ponds[i]); heap.push_back(elem); } make_heap(heap.begin(), heap.end()); for (int i = 0; i < N; i++){ heap[i].pond->heap_index = i; } double time = 0; double first_time = 0; while (heap.size() > 0){ POND* pond = heap[0].pond; pop_heap(heap.begin(), heap.end()); heap.resize(heap.size()-1); for (int i = 0; i < heap.size(); i++){ heap[i].pond->heap_index = i; } pond->full = true; time += pond->remains; double delta_time = pond->remains; for (POND* curr = &(ponds[0]); curr != NULL; curr = curr->next){ curr->adjust_volume(delta_time); } if ((pond->array_index) == (N-1)){ first_time = time; } else { if (pond->next != NULL){(pond->next)->add_rate(pond->rate);} if (pond->prev != NULL){ (pond->prev)->next = pond->next; } } make_heap(heap.begin(), heap.begin() + pond->heap_index + 1); for (int i = 0; i < heap.size(); i++){ heap[i].pond->heap_index = i; } } printf("%.8g %.8g\n", first_time, time); } return 0; }