結果
問題 | No.158 奇妙なお使い |
ユーザー | tottoripaper |
提出日時 | 2015-02-27 00:13:18 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 575 ms / 5,000 ms |
コード長 | 1,421 bytes |
コンパイル時間 | 447 ms |
コンパイル使用メモリ | 57,068 KB |
実行使用メモリ | 47,048 KB |
最終ジャッジ日時 | 2023-09-11 07:52:35 |
合計ジャッジ時間 | 3,200 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 24 ms
46,360 KB |
testcase_01 | AC | 30 ms
46,440 KB |
testcase_02 | AC | 24 ms
46,384 KB |
testcase_03 | AC | 23 ms
46,396 KB |
testcase_04 | AC | 575 ms
47,048 KB |
testcase_05 | AC | 23 ms
46,348 KB |
testcase_06 | AC | 23 ms
46,448 KB |
testcase_07 | AC | 24 ms
46,352 KB |
testcase_08 | AC | 24 ms
46,356 KB |
testcase_09 | AC | 24 ms
46,428 KB |
testcase_10 | AC | 24 ms
46,416 KB |
testcase_11 | AC | 23 ms
46,384 KB |
testcase_12 | AC | 24 ms
46,400 KB |
testcase_13 | AC | 24 ms
46,384 KB |
testcase_14 | AC | 26 ms
46,404 KB |
testcase_15 | AC | 30 ms
46,460 KB |
testcase_16 | AC | 28 ms
46,408 KB |
testcase_17 | AC | 58 ms
46,444 KB |
testcase_18 | AC | 26 ms
46,476 KB |
testcase_19 | AC | 25 ms
46,464 KB |
testcase_20 | AC | 26 ms
46,440 KB |
testcase_21 | AC | 24 ms
46,608 KB |
testcase_22 | AC | 25 ms
47,044 KB |
testcase_23 | AC | 24 ms
46,344 KB |
testcase_24 | AC | 24 ms
46,356 KB |
testcase_25 | AC | 24 ms
46,452 KB |
testcase_26 | AC | 30 ms
46,408 KB |
testcase_27 | AC | 24 ms
46,424 KB |
testcase_28 | AC | 59 ms
46,404 KB |
testcase_29 | AC | 25 ms
46,456 KB |
testcase_30 | AC | 139 ms
46,436 KB |
ソースコード
#include <cstdio> #include <cstring> #include <tuple> #include <vector> #define mt std::make_tuple typedef std::tuple<int,int,int> T; int A[3], Db, B[3], Dc, C[3]; int dp[11][101][10001]; std::vector<T> bv, cv; int rec(int a1, int a2, int a3){ if(dp[a1][a2][a3] != -1){return dp[a1][a2][a3];} int res = 0; for(auto t : bv){ if(a1 >= std::get<0>(t) && a2 >= std::get<1>(t) && a3 >= std::get<2>(t)){ res = std::max(res, 1+rec(a1-std::get<0>(t)+B[0], a2-std::get<1>(t)+B[1], a3-std::get<2>(t)+B[2])); } } for(auto t : cv){ if(a1 >= std::get<0>(t) && a2 >= std::get<1>(t) && a3 >= std::get<2>(t)){ res = std::max(res, 1+rec(a1-std::get<0>(t)+C[0], a2-std::get<1>(t)+C[1], a3-std::get<2>(t)+C[2])); } } return dp[a1][a2][a3] = res; } int main(){ for(int i=0;i<3;i++){scanf("%d", A+i);} scanf("%d", &Db); for(int i=0;i<3;i++){scanf("%d", B+i);} scanf("%d", &Dc); for(int i=0;i<3;i++){scanf("%d", C+i);} for(int i=0;i<=10;i++){ for(int j=0;j<=100;j++){ for(int k=0;k<=10000;k++){ int s = i*1000 + j*100 + k*1; if(s > 10000){continue;} if(s == Db){bv.push_back(mt(i, j, k));} if(s == Dc){cv.push_back(mt(i, j, k));} } } } memset(dp, -1, sizeof(dp)); printf("%d\n", rec(A[0], A[1], A[2])); }