codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

853A.md (2595B)


      1 Source: https://codeforces.com/problemset/problem/853/A
      2 
      3 A. Planning
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are *n* flights that must depart today, the *i*-th of them is planned to depart at the *i*-th minute of the day.
     22 
     23 Metropolis airport is the main transport hub of Metropolia, so it is difficult to keep the schedule intact. This is exactly the case today: because of technical issues, no flights were able to depart during the first *k* minutes of the day, so now the new departure schedule must be created.
     24 
     25 All *n* scheduled flights must now depart at different minutes between (*k* + 1)-th and (*k* + *n*)-th, inclusive. However, it's not mandatory for the flights to depart in the same order they were initially scheduled to do so — their order in the new schedule can be different. There is only one restriction: no flight is allowed to depart earlier than it was supposed to depart in the initial schedule.
     26 
     27 Helen knows that each minute of delay of the *i*-th flight costs airport *c**i* burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.
     28 
     29 Input
     30 
     31 The first line contains two integers *n* and *k* (1 ≤ *k* ≤ *n* ≤ 300 000), here *n* is the number of flights, and *k* is the number of minutes in the beginning of the day that the flights did not depart.
     32 
     33 The second line contains *n* integers *c*1, *c*2, ..., *c**n* (1 ≤ *c**i* ≤ 107), here *c**i* is the cost of delaying the *i*-th flight for one minute.
     34 
     35 Output
     36 
     37 The first line must contain the minimum possible total cost of delaying the flights.
     38 
     39 The second line must contain *n* different integers *t*1, *t*2, ..., *t**n* (*k* + 1 ≤ *t**i* ≤ *k* + *n*), here *t**i* is the minute when the *i*-th flight must depart. If there are several optimal schedules, print any of them.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 5 2  
     47 4 2 1 10 2
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 20  
     54 3 6 7 4 5
     55 ```
     56 
     57 Note
     58 
     59 Let us consider sample test. If Helen just moves all flights 2 minutes later preserving the order, the total cost of delaying the flights would be (3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38 burles.
     60 
     61 However, the better schedule is shown in the sample answer, its cost is (3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20 burles.