522B.md (1743B)
1 Source: https://codeforces.com/problemset/problem/522/B 2 3 B. Photo to Remember 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 One day *n* friends met at a party, they hadn't seen each other for a long time and so they decided to make a group photo together. 22 23 Simply speaking, the process of taking photos can be described as follows. On the photo, each photographed friend occupies a rectangle of pixels: the *i*-th of them occupies the rectangle of width *w**i* pixels and height *h**i* pixels. On the group photo everybody stands in a line, thus the minimum pixel size of the photo including all the photographed friends, is *W* × *H*, where *W* is the total sum of all widths and *H* is the maximum height of all the photographed friends. 24 25 As is usually the case, the friends made *n* photos — the *j*-th (1 ≤ *j* ≤ *n*) photo had everybody except for the *j*-th friend as he was the photographer. 26 27 Print the minimum size of each made photo in pixels. 28 29 Input 30 31 The first line contains integer *n* (2 ≤ *n* ≤ 200 000) — the number of friends. 32 33 Then *n* lines follow: the *i*-th line contains information about the *i*-th friend. The line contains a pair of integers *w**i*, *h**i* (1 ≤ *w**i* ≤ 10, 1 ≤ *h**i* ≤ 1000) — the width and height in pixels of the corresponding rectangle. 34 35 Output 36 37 Print *n* space-separated numbers *b*1, *b*2, ..., *b**n*, where *b**i* — the total number of pixels on the minimum photo containing all friends expect for the *i*-th one. 38 39 Examples 40 41 Input 42 43 ``` 44 3 45 1 10 46 5 5 47 10 1 48 ``` 49 50 Output 51 52 ``` 53 75 110 60 54 ``` 55 56 Input 57 58 ``` 59 3 60 2 1 61 1 2 62 2 1 63 ``` 64 65 Output 66 67 ``` 68 6 4 6 69 ```