結果
問題 | No.158 奇妙なお使い |
ユーザー | knewknowl |
提出日時 | 2015-02-28 16:49:43 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 34 ms / 5,000 ms |
コード長 | 1,336 bytes |
コンパイル時間 | 558 ms |
コンパイル使用メモリ | 60,796 KB |
実行使用メモリ | 47,568 KB |
最終ジャッジ日時 | 2023-09-11 07:54:49 |
合計ジャッジ時間 | 2,266 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 14 ms
46,712 KB |
testcase_01 | AC | 14 ms
46,752 KB |
testcase_02 | AC | 14 ms
46,996 KB |
testcase_03 | AC | 14 ms
46,904 KB |
testcase_04 | AC | 34 ms
47,488 KB |
testcase_05 | AC | 14 ms
46,716 KB |
testcase_06 | AC | 14 ms
46,852 KB |
testcase_07 | AC | 14 ms
46,780 KB |
testcase_08 | AC | 14 ms
46,704 KB |
testcase_09 | AC | 14 ms
46,700 KB |
testcase_10 | AC | 14 ms
46,736 KB |
testcase_11 | AC | 14 ms
46,704 KB |
testcase_12 | AC | 14 ms
47,044 KB |
testcase_13 | AC | 14 ms
46,864 KB |
testcase_14 | AC | 14 ms
46,716 KB |
testcase_15 | AC | 14 ms
46,792 KB |
testcase_16 | AC | 14 ms
46,744 KB |
testcase_17 | AC | 14 ms
46,780 KB |
testcase_18 | AC | 17 ms
46,864 KB |
testcase_19 | AC | 14 ms
46,908 KB |
testcase_20 | AC | 14 ms
46,720 KB |
testcase_21 | AC | 15 ms
47,280 KB |
testcase_22 | AC | 15 ms
47,568 KB |
testcase_23 | AC | 14 ms
46,704 KB |
testcase_24 | AC | 14 ms
46,824 KB |
testcase_25 | AC | 14 ms
46,772 KB |
testcase_26 | AC | 14 ms
46,780 KB |
testcase_27 | AC | 14 ms
46,780 KB |
testcase_28 | AC | 14 ms
46,720 KB |
testcase_29 | AC | 13 ms
47,016 KB |
testcase_30 | AC | 14 ms
46,744 KB |
ソースコード
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int memo[11][101][10001]; int a[3],b[3],c[3]; int bd,cd; struct mon{ int s[3]; }; mon pay(int d){ mon ret;for(int i=0;i<3;++i) ret.s[i]=a[i]; int k = min(ret.s[0],d/1000); ret.s[0]-=k; d-=k*1000; k = min(ret.s[1],d/100); ret.s[1]-=k; d-=k*100; ret.s[2]-=d; return ret; } int dfs(){ // for(int i=0;i<3;++i) cout << a[i] << " "; // cout << endl; if(memo[a[0]][a[1]][a[2]]!=-1) return memo[a[0]][a[1]][a[2]]; mon payb=pay(bd), payc=pay(cd); int ret = 0; mon tmp;for(int i=0;i<3;++i) tmp.s[i]=a[i]; if(payb.s[0]>=0 && payb.s[1]>=0 && payb.s[2]>=0){ for(int i=0;i<3;++i) a[i]=payb.s[i]+b[i]; ret = max(ret,1+dfs()); for(int i=0;i<3;++i) a[i]=tmp.s[i]; } if(payc.s[0]>=0 && payc.s[1]>=0 && payc.s[2]>=0){ for(int i=0;i<3;++i) a[i]=payc.s[i]+c[i]; ret = max(ret,1+dfs()); for(int i=0;i<3;++i) a[i]=tmp.s[i]; } return memo[a[0]][a[1]][a[2]]=ret; } void output(mon m){ for(int i=0;i<3;++i) cout << m.s[i] << " "; cout << endl; } int main(){ memset(memo,-1,sizeof(memo)); for(int i=0;i<3;++i) cin >> a[i]; cin >> bd; for(int i=0;i<3;++i) cin >> b[i]; cin >> cd; for(int i=0;i<3;++i) cin >> c[i]; // output(pay(bd)); // output(pay(cd)); cout << dfs() << endl; return 0; }