結果

問題 No.107 モンスター
コンテスト
ユーザー tokidasakana
提出日時 2025-07-01 15:28:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 5,000 ms
コード長 645 bytes
コンパイル時間 1,725 ms
コンパイル使用メモリ 195,132 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2025-07-01 15:28:59
合計ジャッジ時間 2,873 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

int N,D[16],dp[1<<16][18];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin>>N;
  for(int i=0;i<N;i++)cin>>D[i];
  dp[0][1]=100;
  for(int i=0;i<1<<N;i++){
    for(int j=0;j<N;j++)if(!(i>>j&1)){
      for(int k=1;k<=N;k++)if(dp[i][k]!=0){
        if(D[j]>0){
          dp[i|1<<j][k]=max(dp[i|1<<j][k],min(dp[i][k]+D[j],k*100));
        }else if(dp[i][k]+D[j]>0){
          dp[i|1<<j][k+1]=max(dp[i|1<<j][k+1],dp[i][k]+D[j]);
        }
      }
    }
  }
  int ans=0;
  for(int i=1;i<=N+1;i++)if(dp[(1<<N)-1][i]!=0)ans=max(ans,dp[(1<<N)-1][i]);
  cout<<ans<<'\n';

  return 0;
}
0