#include #include using namespace std; const int MAX_N = 16; int main(){ int n,count = 0; int dp[1 << MAX_N] = {0}; int d[16] = {0}; int tmp = 0; cin >> n; for(int i = 0; i < n; i++) cin >> d[i]; dp[0] = 100;//初期HP for(int i = 0; i < (1 << n); i++){ for(int j = 0; j < n; j++){ if((i >> j) & 1 && (d[j] < 0)){ count++; } } for(int k = 0; k < n; k++){ if(!(i >> k & 1) && dp[i] > 0){//まだk番目のモンスターにあっていない、かつ、HPは0より大きい if(d[k] > 0){//よいモンスター dp[i | 1 << k] = min(100 * (1 + count), dp[i] + d[k] ); }else{//悪いモンスター if(dp[i]+d[k] > 0) tmp = dp[i]+d[k]; else tmp = 0; dp[i | 1 << k] = max(dp[i | 1 << k], tmp); } } } count = 0; } cout << dp[(1 << n) - 1] << endl; return 0; }