Submission #17299

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
int n, m;
int ptn[11] = {0, 1, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
int coin[11];
vector<int> coins;
int memo[100001];
int solve(int val);
int main()
{
cin>> n >> m;
for(int i = 0; i < n; i++) cin>> coin[i];
for(int i = 1; i < ptn[n] + 1; i++) {
int sum = 0;
for(int j = 0; j < n; j++) if(i & 1 << j) sum += coin[j];
if(sum) coins.push_back( sum );
}
memset(memo, -1, sizeof(memo));
cout<< solve(m) <<endl;
return 0;
}
int solve(int val)
{
if(val < 0) return 114514;
if(val == 0) return 0;
if(memo[val] != -1) return memo[val];
int rec = 114514;
for(int i = 0; i < coins.size(); i++) {
rec = min(rec, solve(val - coins[i]) + 1);
}
return memo[val] = rec;
}

ステータス

項目 データ
問題 0088 - レジが壊れた
ユーザー名 ei1538
投稿日時 2017-05-12 17:22:56
言語 C++11
状態 Accepted
得点 5
ソースコード長 836 Byte
最大実行時間 158 ms
最大メモリ使用量 4384 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in-1 AC 10 ms 864 KB
1
in-2 AC 13 ms 928 KB
1
in-3 AC 14 ms 1024 KB
1
in-4 AC 13 ms 4260 KB
1
in-5 AC 10 ms 1440 KB
1
in-6 AC 155 ms 1200 KB
1
in-7 AC 158 ms 1192 KB
1
in-8 AC 144 ms 4384 KB
1
in-9 AC 23 ms 1352 KB
1
in-10 AC 31 ms 1076 KB
1
in-11 AC 12 ms 1348 KB
1
in-12 AC 10 ms 1184 KB
1
in-13 AC 143 ms 1188 KB
1
in-14 AC 26 ms 1096 KB
1
in-15 AC 15 ms 1124 KB
1
in-16 AC 16 ms 996 KB
1
in-17 AC 10 ms 1260 KB
1
in-18 AC 13 ms 872 KB
1
in-19 AC 12 ms 956 KB
1
in-20 AC 15 ms 1016 KB
1
in-21 AC 12 ms 1216 KB
1
in-22 AC 17 ms 1196 KB
1
in-23 AC 11 ms 1080 KB
1
in-24 AC 12 ms 1228 KB
1
in-25 AC 11 ms 1048 KB
1
in-26 AC 14 ms 976 KB
1
in-27 AC 12 ms 1012 KB
1
in-28 AC 11 ms 996 KB
1
in-29 AC 10 ms 984 KB
1
in-30 AC 14 ms 992 KB
1
in-31 AC 11 ms 1336 KB
1
in-32 AC 11 ms 1176 KB
1
in-33 AC 14 ms 1244 KB
1
in-34 AC 12 ms 1180 KB
1
in-35 AC 18 ms 1392 KB
1
in-36 AC 11 ms 1304 KB
1
in-37 AC 10 ms 1384 KB
1
in-38 AC 14 ms 1316 KB
1
in-39 AC 10 ms 1216 KB
1
in-40 AC 10 ms 1236 KB
1
in-41 AC 11 ms 1288 KB
1
in-42 AC 12 ms 1116 KB
1
in-43 AC 20 ms 1040 KB
1
in-44 AC 12 ms 1104 KB
1
in-45 AC 14 ms 1128 KB
1
in-46 AC 11 ms 1020 KB
1
in-47 AC 13 ms 1268 KB
1
in-48 AC 28 ms 1192 KB
1
in-49 AC 11 ms 1396 KB
1
in-50 AC 12 ms 1096 KB
1
in-51 AC 11 ms 1048 KB
1
in-52 AC 14 ms 1336 KB
1
in-53 AC 13 ms 1320 KB
1
in-54 AC 14 ms 1424 KB
1
in-55 AC 14 ms 1212 KB
1
in-56 AC 14 ms 1128 KB
1
in-57 AC 12 ms 1044 KB
1
in-58 AC 9 ms 1128 KB
1
in-59 AC 13 ms 1472 KB
1
in-60 AC 11 ms 1132 KB
1
in-61 AC 15 ms 1380 KB
1
in-62 AC 10 ms 1232 KB
1
in-63 AC 13 ms 1280 KB
1
in-64 AC 14 ms 2672 KB
1
in-65 AC 11 ms 2200 KB
1
in-66 AC 17 ms 1356 KB
1
in-67 AC 15 ms 3192 KB
1
in-68 AC 15 ms 1860 KB
1
in-69 AC 12 ms 2312 KB
1
in-70 AC 36 ms 2544 KB
1
in-71 AC 15 ms 3336 KB
1
in-72 AC 13 ms 1160 KB
1
in-73 AC 12 ms 1224 KB
1
in-74 AC 12 ms 2680 KB
1
in-75 AC 108 ms 3368 KB
1
in-76 AC 11 ms 1640 KB
1
in-77 AC 12 ms 3340 KB
1
in-78 AC 18 ms 3860 KB
1
in-79 AC 16 ms 3448 KB
1
in-80 AC 22 ms 3776 KB
1
in-81 AC 125 ms 3528 KB
1
in-82 AC 16 ms 2864 KB
1
in-83 AC 11 ms 2144 KB
1