結果

問題 No.107 モンスター
コンテスト
ユーザー keiden
提出日時 2024-09-22 12:53:32
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 968 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 30,336 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 12:53:33
合計ジャッジ時間 1,327 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int64_t max(int64_t a, int64_t b) {
    return (a > b ? a : b);
}
int64_t min(int64_t a, int64_t b) {
    return (a < b ? a : b);
}

int main(void) {
    int i, j;
    int N;
    int64_t D[17];
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%" PRIi64, &D[i]);
    }
    int dp[65536];
    for (i = 0; i < 65536; i++) {
        dp[i] = 0;
    }
    dp[0] = 100;
    for (i = 0; i < (1 << N); i++) {
        if (0 == dp[i]) {
            continue;
        }
        int64_t s = 100;
        for (j = 0; j < N; j++) {
            if (((i >> j) & 1) && D[j] < 0) {
                s += 100;
            }
        }
        for (j = 0; j < N; j++) {
            if ((i >> j) & 1) {
                continue;
            }
            int64_t t = i | (1 << j);
            dp[t] = max(dp[t], min(s, dp[i] + D[j]));
        }
    }
    printf("%" PRIi64 "\n", dp[(1 << N) - 1]);
    return 0;
}
0