Cod sursa(job #586821)

Utilizator swift90Ionut Bogdanescu swift90 Data 2 mai 2011 23:20:23
Problema Avioane Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct dfsd{
	long long val,cnt;
}red[100100];
long long N,R,nr[100100],sol,se,sb,ce,cb;
int main(){
	freopen("avioane.in","r",stdin);
	freopen("avioane.out","w",stdout);
	long long i,valoare;
	scanf("%lld",&N);
	for(i=0;i<N;++i)
		scanf("%lld",&nr[i]);
	sort(nr,nr+N);
	R=0;
	for(i=0;i<N;++i){
		if(nr[i]==red[R].val)
			++red[R].cnt;
		else{
			red[++R].val=nr[i];
			red[R].cnt=1;
		}
	}
	ce=N;
	for(i=1;i<=R;++i){
		if(ce*red[i].val>se){
			se=ce*red[i].val;
			valoare=red[i].val;
		}
		ce-=red[i].cnt;
	}
	for(i=R;red[i].val>=valoare;--i){
		cb+=red[i].cnt;
		sb=cb*(red[i].val-valoare);
		if(sb+se>sol)
			sol=sb+se;
	}
	cb=0;
	for(;i>0;--i){
		cb+=red[i].cnt;
		sb=cb*red[i].val;
		if(sb+se>sol)
			sol=sb+se;
	}
	
	printf("%lld\n",sol);
	fclose(stdin);
	fclose(stdout);
	return 0;
}