|
|
this 3 1 1000 90 1000 90 1000 90 2 5 helps me 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[1]+...+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[1]+...+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[1]+...+s[n])*p) ) then we take (s[1]+...+s[j-1])*p (s[0]=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[1]+...+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 Try this test: Input: 5 1 100 0 100 0 100 0 100 0 100 0 2 50 Output: 250 Is it possible to buy several subscriptions? It's not forbidden, but it's never necessary for optimal solution. Each subscription for k or more concerts, you not need more then one. Just why? 4 1 1000 5 1000 5 1000 5 1000 5 2 10 You need to buy two identical subscriptions to get 3600. Ignore my post above, I misunderstood the problem statement. But still, even if you understand, i still don't. In case of 4 1 1000 5 1000 5 1000 5 1000 5 2 10 or even, if we're not allowed to use the same subscription twice, 4 2 1000 5 1000 5 1000 5 1000 5 2 10 2 10 , why can't we have 3600? That is, if i understood you correctly... Try this test: 3 1 1000 0 1000 6 100 10 2 5 answer is: 1985.0 |
|
|