Cod sursa(job #2610832)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 5 mai 2020 18:48:19
Problema Avioane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("avioane.in");
ofstream fout("avioane.out");

long long n,rasp;
long long v[100005];

void solve(int st,int dr,int l,int r)
{
    if(st>dr)return;
    int mij=(st+dr)/2;
    int poz=1;
    long long val=v[mij]*(n-mij+1);
    long long maxi = 0;
    for(int i=l; i<=mij && i<=r; i++)
    {
        if(val+(mij-i)*v[i]>maxi)
        {
            maxi=val+(mij-i)*v[i];
            poz=i;
        }
    }
    rasp=max(rasp,maxi);
    solve(st,mij-1,l,poz);
    solve(mij+1,dr,poz,r);
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    sort(v+1,v+n+1);
    solve(1,n,1,n);
    fout<<rasp;
}