E. Battle Lemmings SOLUTION Codeforces Round #672 (Div. 2)

Battle Lemmings SOLUTION

A beacon manager Peter orders a multitude of n fight lemmings. He requested his military to remain in a line and numbered the lemmings from 1 to n from left to right. A portion of the lemmings hold shields. Every lemming can’t hold more than one shield. 

The more secured Peter’s military is, the better. To figure the assurance of the military, he finds the quantity of secured sets of lemmings, that is such combines that the two lemmings in the pair don’t hold a shield, yet there is a lemming with a shield between them. 

Presently it’s an ideal opportunity to get ready for guard and increment the assurance of the military. To do this, Peter can provide orders. He picks a lemming with a shield and gives him one of the two requests: give the shield to one side neighbor on the off chance that it exists and doesn’t have a shield; give the shield to the correct neighbor on the off chance that it exists and doesn’t have a shield. In one second Peter can provide precisely one request. It’s not satisfactory how much time Peter has before the safeguard. So he chose to decide the maximal estimation of armed force security for every k from 0 to n(n−1)2, in the event that he gives no more that k orders. Help Peter to compute it! 

Info 

First line contains a solitary number n (1≤n≤80), the quantity of lemmings in Peter’s military. 

Second line contains n numbers ai (0≤ai≤1). On the off chance that ai=1, at that point the I-th lemming has a shield, in any case ai=0. 

 

Yield 

Print n(n−1)2+1 numbers, the best conceivable insurance after close to 0,1,… ,n(n−1)2 orders. 

 

Models 

inputCopy 

5

1 0 1

 

outputCopy 

0 2 3 

 

inputCopy 

12 

0 1 0 1 0 

 

outputCopy 

9 12 13 14 15 15 15 15 

 

Note 

Think about the primary model. 

The insurance is at first equivalent to zero, on the grounds that for each pair of lemmings without shields there is no lemmings with shield. 

In one second Peter can arrange the principal lemming give his shield to the correct neighbor. For this situation, the security is two, as there are two ensured sets of lemmings, (1,3) and (1,4). 

In two seconds Peter can act in the accompanying manner. To start with, he arranges the fifth lemming to give a shield to one side neighbor. At that point, he arranges the primary lemming to give a shield to the correct neighbor. For this situation Peter has three secured sets of lemmings — (1,3), (1,5) and (3,5). 

You can ensure that it’s difficult to provide orders so that the security gets more prominent than three.

DOWNLOAD THE SOLUTION

Leave a Comment

close
error: Content is protected !!
Free Udemy Courses and Hacking Resources Join Us on TelegramClick Here
+