結果
問題 | No.158 奇妙なお使い |
ユーザー | ふーらくたる |
提出日時 | 2016-09-17 01:34:54 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 27 ms / 5,000 ms |
コード長 | 1,872 bytes |
コンパイル時間 | 813 ms |
コンパイル使用メモリ | 60,512 KB |
実行使用メモリ | 47,428 KB |
最終ジャッジ日時 | 2023-09-12 04:37:28 |
合計ジャッジ時間 | 2,940 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 13 ms
46,876 KB |
testcase_01 | AC | 13 ms
46,764 KB |
testcase_02 | AC | 14 ms
46,704 KB |
testcase_03 | AC | 14 ms
46,708 KB |
testcase_04 | AC | 27 ms
47,428 KB |
testcase_05 | AC | 13 ms
46,748 KB |
testcase_06 | AC | 14 ms
46,776 KB |
testcase_07 | AC | 14 ms
46,692 KB |
testcase_08 | AC | 13 ms
46,732 KB |
testcase_09 | AC | 13 ms
46,780 KB |
testcase_10 | AC | 13 ms
46,708 KB |
testcase_11 | AC | 13 ms
46,780 KB |
testcase_12 | AC | 13 ms
46,760 KB |
testcase_13 | AC | 13 ms
46,680 KB |
testcase_14 | AC | 13 ms
46,692 KB |
testcase_15 | AC | 14 ms
46,684 KB |
testcase_16 | AC | 14 ms
46,712 KB |
testcase_17 | AC | 14 ms
46,820 KB |
testcase_18 | AC | 15 ms
46,844 KB |
testcase_19 | AC | 13 ms
46,804 KB |
testcase_20 | AC | 13 ms
46,756 KB |
testcase_21 | AC | 14 ms
46,928 KB |
testcase_22 | AC | 14 ms
47,172 KB |
testcase_23 | AC | 14 ms
46,776 KB |
testcase_24 | AC | 13 ms
46,896 KB |
testcase_25 | AC | 13 ms
46,756 KB |
testcase_26 | AC | 14 ms
46,736 KB |
testcase_27 | AC | 13 ms
46,688 KB |
testcase_28 | AC | 13 ms
46,692 KB |
testcase_29 | AC | 14 ms
46,784 KB |
testcase_30 | AC | 13 ms
46,756 KB |
ソースコード
#include <iostream> #include <cstring> #include <tuple> using namespace std; int memo[11][101][10001]; int a1000, a100, a1, db, b1000, b100, b1, dc, c1000, c100, c1; tuple<int, int, int> how_to_pay(int sum, int num1000, int num100, int num1) { int use1000, use100, use1; use1000 = min(sum / 1000, num1000); sum -= use1000 * 1000; use100 = min(sum / 100, num100); sum -= use100 * 100; use1 = min(sum / 1, num1); sum -= use1 * 1; return make_tuple(use1000, use100, use1); } int solve(int num1000, int num100, int num1) { if (memo[num1000][num100][num1] >= 0) { return memo[num1000][num100][num1]; } // 貨幣を大きい方から使っていけば良い int res = 0, use1000, use100, use1; tuple<int, int, int> payment; // Bさんと交換 payment = how_to_pay(db, num1000, num100, num1); use1000 = get<0>(payment); use100 = get<1>(payment); use1 = get<2>(payment); if (1000 * use1000 + 100 * use100 + use1 == db) { res = max(res, solve(num1000 - use1000 + b1000, num100 - use100 + b100, num1 - use1 + b1) + 1); } payment = how_to_pay(dc, num1000, num100, num1); use1000 = get<0>(payment); use100 = get<1>(payment); use1 = get<2>(payment); if (1000 * use1000 + 100 * use100 + use1 == dc) { res = max(res, solve(num1000 - use1000 + c1000, num100 - use100 + c100, num1 - use1 + c1) + 1); } return memo[num1000][num100][num1] = res; } int main() { cin >> a1000 >> a100 >> a1; cin >> db; cin >> b1000 >> b100 >> b1; cin >> dc; cin >> c1000 >> c100 >> c1; memset(memo, -1, sizeof(memo)); cout << solve(a1000, a100, a1) << endl; return 0; }