Cod sursa(job #1585595)

Utilizator theodorstoica313CbTheodor Nicolae Stoica theodorstoica313Cb Data 31 ianuarie 2016 11:41:56
Problema Avioane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,i,j,ras,sum,ma,k,a[100004],s[100004];
double l[100004];
double inter(long long i, long long j)
{
    return (double) ((1-j)*a[j]-(1-i)*a[i])/(a[i]-a[j]);
}
int main()
{
    freopen("avioane.in","r",stdin);
    freopen("avioane.out","w",stdout);
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    //draw 2X-0, 2X-2, 9X-18, 15X-45,17X-68, 18X-90, 20X-120, 20X-140, 27X-216, 29X-261
    //for(i=1;i<=n;i++)printf("%dX-%d, ",a[i],(i-1)*a[i]);printf("\n");
/*
    for(i=2;i<=n;i++)
    {
        ras=a[i]*(n-i+1);
        for(j=1;j<i;j++)
        {
            ras1=ras+a[j]*(i-j);
            if(ras1>ma)
                ma=ras1;
        }
    }
    printf("%d\n",ma);
    */
    l[1]=0.0;
    s[1]=1;
    k=1;
    for(i=2;i<=n;i++)
    {
        if(a[i]!=a[i-1])
        {
            while(k&&inter(i,s[k])<=l[k])
            {
                l[k]=0;
                k--;
            }
            k++;
            l[k]=inter(i,s[k-1]);
            s[k]=i;
        }
    }
    j=1;
    ras=0;
    for(i=1;i<=n;i++)
    {
        while(i>l[j]&&j<k)j++;
        sum=a[s[j-1]]*(i-s[j-1])+a[i]*(n-i+1);
        if(ras<sum)ras=sum;
    }
    printf("%lld",ras);
    return 0;
}