Advertisement blocking software were detected ;( Please add this webpage to whitelist.

CADYDIST - Candy Distribution

Alice is a teacher that loves her students. As the school year reaches its end, she wants to reward all her students with candies for all their hard work.

Since each of her classes is unique, she decided she’ll give a different kind of candy for each class, and in order to avoid students being mad at others in their class, she wants to make things fair by giving all students in the same class the same kind of candy.

Happily, she went to the candy shop, and fortunately found out that it had N different types of candy, exactly the same number of classes of students she taught!

Looking at the prices and paying close attention to the number of students in each class, Alice noted that she could save some money by assigning the types of candy to certain classes. Because she’s a teacher, her income is not that big and saving money is very important to her, so she asked you to write a program to determine the least amount of money she must spend.


Each test case consists of three lines. The first line contains a positive integer N (1≤N≤100000). The second line contains N integers Ci, the ith integer indicates the number of students in Alice’s i-th class. The third and last line also contains N integers Pi the ith integer indicates the price of the ith type of candy (1 ≤ Ci, Pi  ≤ 100000).

The input ends with a line consisting of a 0, which indicates end of input.


For each test case, output a line containing the least amount of money Alice must spend.


1 1 1 1
2 2 2 2
10 80 37 22 109
6 8 8 20 15
0 Output: 8

hide comments
suraj_ch77: 2015-09-19 11:21:06

why to cry for the data type problem?

gullu_mishra: 2015-09-17 23:14:59

in 1 go :)

Abishek: 2015-09-13 17:37:56

use merge sort and normal multiplication .. try FASHION after this . similar concept :)

vishrut mishra: 2015-08-17 21:07:42

use everything as a long long int, it'll save you a lot of WAs.

fool_01: 2015-08-17 15:41:33

For TLE, use printf,scanf . For wrong ans check overflows

Liquid_Science: 2015-08-05 16:04:18

got accepted after using long instead of int
constraints stated seems to be wrong -_-
btw my code with long used for sum failed so something is wrong defo

Last edit: 2015-08-05 16:09:58
xyz: 2015-07-09 13:02:37

use unsigned long long int...

SangKuan: 2015-07-04 02:21:38

greedy algorithm.and use quicksort or mergesort,do not use Selection sort or insert sort,it is O(n^2).and can use auto sorted struct,like priority_queue

Last edit: 2015-07-04 03:50:06
Bhuvnesh Jain: 2015-06-25 22:01:40

similar to problem FASHION

sujit yadav: 2015-06-23 16:07:35

greedy !! :)

Added by:Paulo Costa
Time limit:0.301s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Resource:ITA - Brazilian ICPC Training Camp, Jan-Feb/2012