Submission #00134

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
int n;
int m[15];
int dp[1 << 16][1001];
int solve(int stat, int sum) {
if(dp[stat][sum] != -1) return dp[stat][sum];
if(stat == (1 << n) - 1) return 0;
int ret = 1 << 24;
for(int i = 0; i < n; ++i) {
if(!((stat >> i) & 1)) {
/*
if(m[i] > sum % 1000) {
ret = min(ret, solve(stat | (1 << i), sum + m[i]) + m[i] - sum % 1000);
} else {
ret = min(ret, solve(stat | (1 << i), sum + m[i]));
}
*/
if(m[i] > sum) {
ret = min(ret, solve(stat | (1 << i), (sum + m[i]) % 1000) + m[i] - sum);
} else {
ret = min(ret, solve(stat | (1 << i), (sum + m[i]) % 1000));
}
}
}
return dp[stat][sum] = ret;
}
int main() {
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> m[i];
}
memset(dp, -1, sizeof(dp));
cout << solve(0, 0) << endl;
}

ステータス

項目 データ
問題 0007 - 森田氏の欲求
ユーザー名 ei1503
投稿日時 2016-05-14 15:54:15
言語 C++11
状態 Accepted
得点 13
ソースコード長 1049 Byte
最大実行時間 49 ms
最大メモリ使用量 256976 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
case1.txt AC 44 ms 256732 KB
1
case2.txt AC 46 ms 256752 KB
1
case3.txt AC 45 ms 256764 KB
1
case4.txt AC 43 ms 256892 KB
1
case5.txt AC 41 ms 256976 KB
1
case6.txt AC 45 ms 256952 KB
1
case7.txt AC 44 ms 256804 KB
1
case8.txt AC 46 ms 256780 KB
1
case9.txt AC 44 ms 256756 KB
1
case10.txt AC 42 ms 256712 KB
1
case11.txt AC 42 ms 256688 KB
1
case12.txt AC 43 ms 256792 KB
1
case13.txt AC 42 ms 256644 KB
1
case14.txt AC 45 ms 256624 KB
1
case15.txt AC 45 ms 256732 KB
1
case16.txt AC 46 ms 256840 KB
1
case17.txt AC 42 ms 256812 KB
1
case18.txt AC 49 ms 256792 KB
1
case19.txt AC 45 ms 256772 KB
1
case20.txt AC 42 ms 256728 KB
1
case21.txt AC 46 ms 256708 KB
1
case22.txt AC 43 ms 256944 KB
1
case23.txt AC 41 ms 256924 KB
1
case24.txt AC 43 ms 256896 KB
1
case25.txt AC 43 ms 256876 KB
1
case26.txt AC 43 ms 256856 KB
1
case27.txt AC 39 ms 256828 KB
1
case28.txt AC 45 ms 256936 KB
1
case29.txt AC 46 ms 256916 KB
1
case30.txt AC 41 ms 256740 KB
1
case31.txt AC 44 ms 256844 KB
1
case32.txt AC 39 ms 256948 KB
1
case33.txt AC 41 ms 256928 KB
1
case34.txt AC 42 ms 256904 KB
1
case35.txt AC 41 ms 256876 KB
1
case36.txt AC 42 ms 256860 KB
1
case37.txt AC 46 ms 256832 KB
1
case38.txt AC 45 ms 256812 KB
1
case39.txt AC 43 ms 256792 KB
1
case40.txt AC 44 ms 256868 KB
1
sample1.txt AC 43 ms 256856 KB
1
sample2.txt AC 44 ms 256832 KB
1
sample3.txt AC 44 ms 256812 KB
1