Cod sursa(job #2605654)

Utilizator FrostfireMagirescu Tudor Frostfire Data 25 aprilie 2020 17:04:20
Problema Avioane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 100000

using namespace std;

ifstream f("avioane.in");
ofstream g("avioane.out");

int n, v[NMAX+10];
long long ans;

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

int main()
{
    f >> n;
    for(int i=1; i<=n; i++) f >> v[i];
    sort(v+1, v+n+1);
    solve(1, n, 1, n);
    g << ans << '\n';
    return 0;
}