結果
問題 | No.107 モンスター |
ユーザー |
![]() |
提出日時 | 2017-01-10 18:31:26 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 68 ms / 5,000 ms |
コード長 | 1,484 bytes |
コンパイル時間 | 1,603 ms |
コンパイル使用メモリ | 147,804 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 06:17:33 |
合計ジャッジ時間 | 2,945 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
import std.algorithm;import std.array;import std.ascii;import std.container;import std.conv;import std.math;import std.numeric;import std.range;import std.stdio;import std.string;import std.typecons;void log(A...)(A arg) { stderr.writeln(arg); }int size(T)(in T s) { return cast(int)s.length; }void main() {int N; readf("%d\n", &N);auto D = readln.chomp.split(" ").map!(to!int).array;const INF = int.max / 8;int[int] memo;int f(int set) {if (set == 0) return 100;if (set in memo) return memo[set];int next_hp(int cur_hp, int mid, int bit) { // mid: monster id, bit: 蛟偵@縺溘Δ繝ウ繧ケ繧ソ繝シ縺ョid縺ョ髮・粋int max_hp = 100;if (D[mid] < 0) {return cur_hp + D[mid] <= 0 ? -INF : cur_hp + D[mid];} else {for (int i = 0; i < N; i++) {if (bit & (1 << i)) {if (D[i] < 0) max_hp += 100;}}return min(cur_hp + D[mid], max_hp);}}int ans = -INF;for (int i = 0; i < N; i++) {if (set & (1 << i)) {int hp = next_hp(f(set - (1 << i)), i, set);ans = max(ans, hp);}}return memo[set] = ans;}writeln(max(0, f((1 << N) - 1)));// foreach (k, v; memo) {// log(k, " -> ", v);// }}