結果
問題 | No.158 奇妙なお使い |
ユーザー | tnakao0123 |
提出日時 | 2016-03-23 16:25:46 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 29 ms / 5,000 ms |
コード長 | 1,716 bytes |
コンパイル時間 | 756 ms |
コンパイル使用メモリ | 83,092 KB |
実行使用メモリ | 47,144 KB |
最終ジャッジ日時 | 2023-09-11 23:55:43 |
合計ジャッジ時間 | 2,683 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 13 ms
46,936 KB |
testcase_01 | AC | 13 ms
46,984 KB |
testcase_02 | AC | 12 ms
46,884 KB |
testcase_03 | AC | 12 ms
46,880 KB |
testcase_04 | AC | 29 ms
47,068 KB |
testcase_05 | AC | 13 ms
46,916 KB |
testcase_06 | AC | 14 ms
46,880 KB |
testcase_07 | AC | 13 ms
46,936 KB |
testcase_08 | AC | 13 ms
46,932 KB |
testcase_09 | AC | 12 ms
47,072 KB |
testcase_10 | AC | 13 ms
46,856 KB |
testcase_11 | AC | 13 ms
46,884 KB |
testcase_12 | AC | 13 ms
46,936 KB |
testcase_13 | AC | 13 ms
47,084 KB |
testcase_14 | AC | 13 ms
46,928 KB |
testcase_15 | AC | 13 ms
46,872 KB |
testcase_16 | AC | 13 ms
46,888 KB |
testcase_17 | AC | 14 ms
46,892 KB |
testcase_18 | AC | 16 ms
46,932 KB |
testcase_19 | AC | 13 ms
47,012 KB |
testcase_20 | AC | 13 ms
46,944 KB |
testcase_21 | AC | 27 ms
47,076 KB |
testcase_22 | AC | 26 ms
46,868 KB |
testcase_23 | AC | 13 ms
47,136 KB |
testcase_24 | AC | 13 ms
46,876 KB |
testcase_25 | AC | 12 ms
46,888 KB |
testcase_26 | AC | 13 ms
46,888 KB |
testcase_27 | AC | 14 ms
47,140 KB |
testcase_28 | AC | 13 ms
46,932 KB |
testcase_29 | AC | 14 ms
47,144 KB |
testcase_30 | AC | 13 ms
46,988 KB |
ソースコード
/* -*- coding: utf-8 -*- * * 158.cc: No.158 奇妙なお使い - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 10000; const int MAX_C0 = 10; const int MAX_C1 = 100; /* typedef */ /* global variables */ int dp[MAX_N + 1][MAX_C0 + 1][MAX_C1 + 1]; /* subroutines */ bool pay(int d, int a0, int a1, int a2, int &b0, int &b1, int &b2) { b0 = min(d / 1000, a0); b1 = min((d - 1000 * b0) / 100, a1); b2 = d - 1000 * b0 - 100 * b1; return (a2 >= b2); } /* main */ int main() { int a0, a1, a2; cin >> a0 >> a1 >> a2; int db, b0, b1, b2; cin >> db >> b0 >> b1 >> b2; int dc, c0, c1, c2; cin >> dc >> c0 >> c1 >> c2; memset(dp, -1, sizeof(dp)); dp[0][a0][a1] = a2; int maxd = 0; bool cont = true; for (int i = 0; cont && i <= MAX_N; i++) { cont = false; for (int j = 0; j <= MAX_C0; j++) for (int k = 0; k <= MAX_C1; k++) { int d0 = dp[i][j][k]; if (d0 >= 0) { int x0, x1, x2; if (pay(db, j, k, d0, x0, x1, x2)) { int jb = j - x0 + b0, kb = k - x1 + b1, d1 = d0 - x2 + b2; if (dp[i + 1][jb][kb] < d1) dp[i + 1][jb][kb] = d1, cont = true, maxd = i + 1; } if (pay(dc, j, k, d0, x0, x1, x2)) { int jc = j - x0 + c0, kc = k - x1 + c1, d1 = d0 - x2 + c2; if (dp[i + 1][jc][kc] < d1) dp[i + 1][jc][kc] = d1, cont = true, maxd = i + 1; } } } } printf("%d\n", maxd); return 0; }