Cod sursa(job #2611551)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 7 mai 2020 01:03:39
Problema Avioane Scor 80
Compilator cpp-64 Status done
Runda antrenament_ Marime 0.62 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,v[100005],d[100005];
unsigned int sol=0;

void rez(int st,int dr,int r,int l)
 {
  if(st>dr) return;
  int mid=(st+dr)/2,cap;
  unsigned int maxim=0;
  for(int i=r;i<=l&&i<mid;i++)
    {
     if( (mid-i)*v[i]>maxim )
      {
       maxim=(mid-i)*v[i];
       cap=i;
      }
    }
  d[mid]=cap;
  maxim+=(n-mid+1)*v[mid];
  sol=max(sol,maxim);
  rez(mid+1,dr,d[mid],l);
  rez(st,mid-1,r,d[mid]);
 }

int main()
{
f>>n;
for(int i=1;i<=n;i++) f>>v[i];
sort(v+1,v+n+1);
rez(1,n,1,n);
g<<sol;
}