PROBLEM LINK:Author: Admin2 DIFFICULTY:Easy PREREQUISITES:Greedy,Heap PROBLEM:You have an upcoming camp. There are N trainers. The camp runs for D days.Each day,there can be at most one lecture. The i^{th} trainer arrives on day D_{i} and then stays till the end of the camp. He also wants to teach exactly T_{i} lectures. For each lecture that a trainer was not able to teach,his sadness level will be increased by S_{i}. You are the main organizer of the contest. You want to find minimum total sadness of the trainers. EXPLANATION:Let's assign our trainers starting from the first day of the camp. At each day adding arriving trainers to our set of trainers. Each day should be assigned to only one trainer, it's obvious that we should assign the trainer with maximum sadness to this lecture, so our set (container) should be a heap sorting trainers by their sadness value. In fact we should know also the number of days each lecturer wants to serve in, so we take the lecturer with maximum sadness from our heap and decrease his demand by 1. In case he still has lectures he would like to do, we keep him in the heap, otherwise we just pop him out. After finishing all days, some teachers may have some remaining lectures they wanted to teach but we couldn't find such days for them. Let's denote the number of lectures the i^{th} trainer couldn't teach by rem_{i} So our answer would be : $answer = \sum_{i=1}^{i=N} rem_i * S_i$ AUTHOR'S AND TESTER'S SOLUTIONS:AUTHOR's solution: Will be found here
This question is marked "community wiki".
asked 15 Jul '17, 07:23

I have used Segment Trees answered 17 Jul '17, 16:52

@lord_ozb: You have used a double loop here which caused the time to exceed the limit.
answered 18 Jul '17, 09:05

Can anyone help me? Author solution I seem that complexity O(N*T).Here N=100000 and T=100000 according to Constraints.How it's passed all test case.May be something i miss.Thanks in advance. answered 20 Jul '17, 20:47

community  need help to understand what is missing https://www.codechef.com/viewsolution/14559868. only 40 pts answered 17 Jul '17, 18:58

Can anyone explain where I went wrong? 40 pts. answered 17 Jul '17, 21:26

Hi! The link to practice and main contest are incorrect. Please update. answered 18 Jul '17, 08:32

can anyone explain why i m getting WA for last 2 subtask. https://www.codechef.com/viewsolution/14601668 answered 18 Jul '17, 09:05
