結果

問題 No.158 奇妙なお使い
ユーザー なおなお
提出日時 2015-02-27 00:18:46
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 55 ms / 5,000 ms
コード長 1,568 bytes
コンパイル時間 1,227 ms
コンパイル使用メモリ 158,204 KB
実行使用メモリ 57,344 KB
最終ジャッジ日時 2024-06-28 22:23:30
合計ジャッジ時間 3,385 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define FOR(i, f, t)        for(int(i)=(f);(i)<(t);(++i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))
const int MOD = int(1e9+7);

int A1000,A100,A1;
int DB,DC;
int B1000,B100,B1;
int C1000,C100,C1;

int memo[11][111][11111];

int dfs(int a1000, int a100, int a1){
    int maxv = 0;
    if(memo[a1000][a100][a1] >= 0) return memo[a1000][a100][a1];
    {
        int k1000 = a1000, k100 = a100, k1 = a1;
        int db = DB;
        while(k1000 && db >= 1000) k1000--, db -= 1000;
        while(k100  && db >=  100) k100--,  db -= 100;
        if(k1 >= db) k1 -= db, db = 0;
        if(db == 0){
            maxv = max(maxv, dfs(k1000+B1000,k100+B100,k1+B1)+1);
        }
    }
    {
        int k1000 = a1000, k100 = a100, k1 = a1;
        int dc = DC;
        while(k1000 && dc >= 1000) k1000--, dc -= 1000;
        while(k100  && dc >=  100) k100--,  dc -= 100;
        if(k1 >= dc) k1 -= dc, dc = 0;
        if(dc == 0){
            maxv = max(maxv, dfs(k1000+C1000,k100+C100,k1+C1)+1);
        }
    }
    return memo[a1000][a100][a1] = maxv;
}

int main(){
    do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0);
    cin >> A1000 >> A100 >> A1;
    cin >> DB;
    cin >> B1000 >> B100 >> B1;
    cin >> DC;
    cin >> C1000 >> C100 >> C1;

    memset(memo, -1, sizeof(memo));
    cout << dfs(A1000,A100,A1) << endl;

    return 0;
}
0