ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 2092. Bolero

What is the best asymptotics?
Posted by Felix_Mate 28 Jun 2017 15:11
My algo is O(p*n*logn).

Algo:
1)sort pairs <d,s> by d.  We get d1<=d2<=d3<=...<=dn.
s1  s2  s3       sn
2)For each p we choose a minimal k (if exist pairs <ki,p> and <kj,p> where ki<kj then we delete <kj,p>

3)ans=s+...+s[n]-(x1+x2+...+xn)/100 where xi=s[i]*di or xi=s[i]*p if we choose p (if we choose p => the minimum of the k elements of x are equal to s*p), i=1..n

=> we must max_sum=(x1+x2+...+xn)->max
=>ans=s+...+s[n]-max_sum/100

4)max_sum=s1*d1+...+sn*dn
For each p=1..100 find 1<=j<=n | p<dj, j->min (if there is no such j => max_sum=max(max_sum, (s+...+s[n])*p) )
then we take (s+...+s[j-1])*p (s=0); if we took <k elements then we must take lost=k-(j-1) elements from sj,...,sn. We must choose such index i1<i2<...<ilost from j..n | s[i1]*(d[i1]-p)=min(s[i]*(d[i]-p), j<=i<=n, s[i2]*(d[i2]-p)=min(s[i]*(d[i]-p), j<=i<=n,i!=i1, ... .
then max_sum=max(max_sum, (s+...+s[j-1])*p + (s[i1]+...+s[ilost])*p+Sum(si*di, j<=i<=n and i<>ik,k=1..lost)).

Edited by author 28.06.2017 15:34