PriorityQueue
SRM 692 · 2016-06-04 · by Xellos0
Problem Statement
It's lunchtime! The school canteen is currently empty. N children are going to enter the canteen and form a single queue. The children are numbered 0 through N-1 in the order in which they enter the canteen. Whenever a child enters the canteen, it performs one of two possible actions:
- either it stands at the current end of the lunch queue,
- or it skips the entire queue and goes to stand at its current beginning.
You are given the description of the children's behaviour: a
You are also given a
At the beginning, the displeasure of each child is zero. The displeasure D[i] of child i grows whenever another child cuts in front of them. More precisely, whenever child i already stands in the queue and child j goes to the beginning of the queue, the displeasure of child i will grow by a[i].
The total displeasure is the sum of all D[i]. Compute and return the total displeasure after all N children have joined the queue.
Constraints
- N will be between 1 and 100, inclusive.
- The string S will contain N characters.
- a will contain N elements.
- Each element of a will be between 1 and 1,000, inclusive.
"bbbbb"
{1,1,1,1,1}
Returns: 10
The queue will look as follows: { child 4, child 3, child 2, child 1, child 0 }. The individual displeasures at the end are D[0] = 4, D[1] = 3, D[2] = 2, D[3] = 1, and D[4] = 0. Thus, the total displeasure is 4+3+2+1+0 = 10.
"eeeeee"
{416,5,41,96,965,7}
Returns: 0
"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
{1,3,5,41,16,1,5,26,51,5,1,6,1,22,1,15,5,15,451,6,1,651,651,851,51,51,511,5,41,85,20,88,11,185,5,77,723,960,620,397,484,692,600,477,222,514,197,131,418,105,130,480,538,727,422,694,224,727,499,810,601,352,33,713,80,217,606,39,676,28,283,207,743,40,688,130,557,793,473,907,332,561,367,890,638,997,461,886,445,47,358,366,371,19,97,412,725,102,153,810}
Returns: 1239716
"eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"
{872,272,446,900,294,800,565,428,958,71,478,294,856,925,387,719,760,613,45,980,520,921,448,377,296,191,643,357,207,47,455,442,451,721,16,150,706,191,824,737,772,26,178,451,327,509,897,551,562,627,705,883,796,365,501,141,32,141,910,859,359,959,589,633,472,597,305,57,111,885,674,961,593,873,726,313,568,124,434,877,192,618,271,149,979,91,145,60,861,537,54,307,125,192,362,277,151,55,379,951}
Returns: 0
"b"
{1000}
Returns: 0
"bee"
{50,40,30}
Returns: 0
When the first child joins the queue, there are no other children in the queue yet, so all displeasures remain at zero. The other two children stand at the end of the queue, so they don't change anyone's displeasure either. The total displeasure at the end is therefore 0.
"beeebeeeeee"
{743,522,871,408,717,878,746,587,481,263,701}
Returns: 2544
random
"bbbebbbbebbbbebbbbbbeebeeeeebbbbbb"
{347,697,133,17,258,649,33,229,572,800,229,119,811,311,305,167,534,56,27,167,911,252,71,731,579,255,456,330,36,618,1000,871,156,211}
Returns: 133603
random
"bbbbbeebbbbbebbebbbeeebbeebbbbebebbeeebeebbbebbbebbbbebebbeeebbbbeebebebbebbbbebbb"
{508,14,683,129,155,409,849,183,627,117,532,481,211,959,88,906,996,360,24,198,919,821,354,607,933,196,854,281,913,339,410,983,285,230,221,813,526,229,535,960,373,362,6,572,265,131,843,59,715,421,646,489,584,53,679,727,461,294,242,754,6,954,688,290,600,271,189,691,40,810,65,584,374,458,158,685,834,328,759,136,85,995}
Returns: 998393
random
"ebebbebbbeeeebbeeebebbbbbeebbebbbeebbbebbbeebbebebebeebebbeeebbeeeebbbeeebb"
{219,85,927,420,314,582,307,897,597,384,369,819,682,986,50,593,297,738,102,189,152,659,22,38,449,971,641,412,366,500,342,888,571,555,358,855,186,956,797,483,320,472,254,373,57,102,681,860,239,405,748,560,796,690,529,731,115,594,761,198,63,146,988,610,351,534,714,790,393,531,981,284,144,807,831}
Returns: 689296
random
"bbebbeeee"
{827,583,432,555,659,246,208,24,432}
Returns: 5066
random
"bbebbeebbbbebbbbebbbbbbbbbebebbeb"
{370,636,620,941,880,870,51,343,914,342,181,827,446,58,537,563,978,299,571,148,721,9,76,851,825,181,411,484,673,33,165,562,507}
Returns: 213671
random
"bbbeeeebebbbbebbbbbeb"
{723,134,601,856,471,907,381,386,523,907,269,257,553,400,945,994,749,616,515,323,25}
Returns: 86323
random
"ebbbeeeebbebbeebbee"
{457,379,108,115,930,600,755,136,179,409,778,778,297,198,566,58,154,938,911}
Returns: 33274
random
"ebbbeeeeebeeeeebeebeeebbbbebbbbebebbbebbebebebbebebbbebeebebeeebebbbbeeebebebbbbeebbeebbebeeeb"
{501,290,451,792,978,110,843,104,121,133,952,20,31,224,594,432,255,931,684,914,31,620,480,928,809,857,762,398,301,253,954,72,333,443,371,663,699,382,610,545,677,626,381,801,701,36,126,148,650,669,679,128,628,948,986,680,57,733,569,361,518,766,982,274,73,736,438,204,57,628,876,550,223,747,369,898,956,911,220,580,527,11,817,318,477,988,556,945,773,694,510,7,469,519}
Returns: 1172856
random
Submissions are judged against all 37 archived test cases, of which 15 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PriorityQueue with a public method int findAnnoyance(string S, vector<int> a) · 37 test cases · 2 s / 256 MB per case