結果

問題 No.286 Modulo Discount Store
ユーザー veqcc
提出日時 2019-02-16 15:55:07
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 9 ms
コード長 945 Byte
コンパイル時間 675 ms
使用メモリ 1,636 KB
最終ジャッジ日時 2019-09-25 18:46:01

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 4 ms
1,508 KB
case2.txt AC 4 ms
1,512 KB
case3.txt AC 5 ms
1,544 KB
case4.txt AC 3 ms
1,512 KB
case5.txt AC 3 ms
1,512 KB
case6.txt AC 3 ms
1,512 KB
case7.txt AC 6 ms
1,572 KB
case8.txt AC 3 ms
1,512 KB
case9.txt AC 3 ms
1,508 KB
case10.txt AC 3 ms
1,508 KB
case11.txt AC 4 ms
1,528 KB
case12.txt AC 4 ms
1,508 KB
case13.txt AC 3 ms
1,508 KB
case14.txt AC 5 ms
1,540 KB
case15.txt AC 4 ms
1,512 KB
case16.txt AC 3 ms
1,512 KB
case17.txt AC 4 ms
1,512 KB
case18.txt AC 9 ms
1,636 KB
case19.txt AC 3 ms
1,528 KB
case20.txt AC 3 ms
1,512 KB
case21.txt AC 3 ms
1,512 KB
case22.txt AC 3 ms
1,508 KB
case23.txt AC 3 ms
1,508 KB
case24.txt AC 5 ms
1,544 KB
case25.txt AC 3 ms
1,508 KB
case26.txt AC 3 ms
1,520 KB
case27.txt AC 4 ms
1,512 KB
case28.txt AC 4 ms
1,520 KB
case29.txt AC 6 ms
1,572 KB
case30.txt AC 3 ms
1,512 KB
case31.txt AC 4 ms
1,508 KB
case32.txt AC 4 ms
1,512 KB
case33.txt AC 3 ms
1,508 KB
case34.txt AC 3 ms
1,512 KB
case35.txt AC 3 ms
1,512 KB
case36.txt AC 3 ms
1,512 KB
case37.txt AC 3 ms
1,508 KB
case38.txt AC 3 ms
1,516 KB
case39.txt AC 3 ms
1,512 KB
case40.txt AC 5 ms
1,576 KB
sample1.txt AC 3 ms
1,512 KB
sample2.txt AC 4 ms
1,508 KB
sample3.txt AC 3 ms
1,508 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int n, m[15], dp[1 << 15];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> m[i];

    for (int i = 0; i < (1 << n); i++) {
        // 集合iを買った時の値引額
        int discount = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) discount += m[j];
        }
        discount %= 1000;

        // 新たに商品jを買う
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) continue;

            int sm = i | (1 << j);
            int cost = max(0, m[j] - discount);
            dp[sm] = dp[sm] ? min(dp[sm], dp[i] + cost) : dp[i] + cost;
        }
    }

    cout << dp[(1 << n) - 1] << "\n";
    return 0;
}
0