Cod sursa(job #2636351)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 17 iulie 2020 17:09:47
Problema Avioane Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>
#define MAX 131072
#define MOD 98999
#define INF 2100000000
#define eps 1e-5

using namespace std;
const int NMAX = 100100;

FILE *IN, *OUT;

int N;
int v[NMAX];
long long ans;

int pos, sign, out;
char f[MAX], Out[NMAX], str[10];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

void read(){
    Read(N);
    for(int i = 1; i <= N; i++)
        Read(v[i]);
    sort(v + 1, v + N + 1);
}

void dei(int st, int dr, int l, int r){
    if(st > dr) return;
    int mid = (st + dr) / 2, idx;
    long long val = v[mid] * (N - mid + 1), vMax = -1;
    for(int i = l; i <= mid && i <= r; i++)
        if(val + v[i] * (mid - i) > vMax){
            vMax = val + v[i] * (mid - i);
            idx = i;
        }
    ans = max(ans, vMax);
    dei(st, mid - 1, l, idx);
    dei(mid + 1, dr, idx, r);
}

int main(){

    IN = fopen("avioane.in", "r");
    OUT = fopen("avioane.out", "w");

    read();
    dei(1, N, 1, N);
    fprintf(OUT, "%lld", ans);

    return 0;
}