#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define INF 100000000 #define EPS 1e-9 #define Pi acos(-1) using namespace std; typedef long long ll; #define MAX_N 16 int N; int D[MAX_N]; int dp[1 << MAX_N]; //S:倒した敵 currentLife:現在の体力 int solve(int S, int currentLife){ if (dp[S] != -1) return dp[S]; if (S == (1 << N) - 1) return currentLife; int maxLife = 100; for (int i = 0; i < N; i++){ if ((S >> i) & 1 && D[i] < 0) maxLife += 100; } //cout << "計算now S: " << S << " currentLife: " << currentLife << " maxLife: " << maxLife << endl; int num = 0; for (int i = 0; i < N; i++){ if (!((S >> i) & 1)){ if (D[i] > 0){ num = max(num, solve(S | (1 << i), min(maxLife, currentLife + D[i]))); } else if(D[i] < 0 && currentLife + D[i] > 0){ num = max(num, solve(S | (1 << i), currentLife + D[i])); } } } return dp[S] = num; } int main(){ cin >> N; for (int i = 0; i < N; i++){ cin >> D[i]; } memset(dp, -1, sizeof(dp)); cout << solve(0, 100) << endl; return 0; }