Creador de Grafos - 40pts (PA) [Terminar]

gistfile1.cpp

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define sz size
#define PS push
using namespace std;
typedef long long int lli;
int N;
int A[52]={0};
stack<int> G[52];
lli answer = 0;
lli intentos = 0;
void busqueda(int limit, int idx, lli suma, lli acum){
	int i;
	if(intentos>5000000){
		return;
	}
	++intentos;
	if(idx>N){
		if(suma>answer){
			answer = suma;
		}
		return;
	}
	if(limit>0){
		for(i=1; i<=limit; ++i){
			if(acum){
				acum -= 1;
				busqueda(limit-i, idx+1, suma+A[i+1], acum+i);
			} else {
				busqueda(limit-i, idx+1, suma+A[i], acum+i);
			}
		}
	} else {
			busqueda(limit, N+1, suma+((N-idx+1) * A[1]), acum);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int i;
	cin>>N;
	for(i=1; i<N; ++i){
		cin>>A[i];
		if(A[i]>answer){
			answer=A[i];
		}
	}
	sort(A, A+(N-1));
	busqueda(N-1,1,0,0);
	cout << answer << endl;
	return 0;
}