結果

問題 No.158 奇妙なお使い
ユーザー GOTKAKO
提出日時 2025-09-02 12:00:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 369 ms / 5,000 ms
コード長 1,213 bytes
コンパイル時間 2,102 ms
コンパイル使用メモリ 203,912 KB
実行使用メモリ 50,816 KB
最終ジャッジ日時 2025-09-02 12:00:38
合計ジャッジ時間 5,968 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector dp(11,vector(101,vector(10001,-1)));
    int a,b,c; cin >> a >> b >> c;
    dp.at(a).at(b).at(c) = 0;

    int db,b3,b2,b1; cin >> db >> b3 >> b2 >> b1;
    int dc,c3,c2,c1; cin >> dc >> c3 >> c2 >> c1;


    int answer = 0;
    for(int sum=10000; sum>=0; sum--){
        for(a=0; a*1000<=sum; a++) for(int b=0; a*1000+b*100<=sum; b++){
            int c = sum-a*1000-b*100;
            if(dp.at(a).at(b).at(c) == -1) continue;
            int d = dp[a][b][c];
            for(int x=0; x*1000<=db&&x<=a; x++) for(int y=0; x*1000+y*100<=db&&y<=b; y++){
                int z = db-x*1000-y*100;
                if(z > c) continue;
                int &d2 = dp[a-x+b3][b-y+b2][c-z+b1];
                d2 = max(d2,d+1);
            }
            for(int x=0; x*1000<=dc&&x<=a; x++) for(int y=0; x*1000+y*100<=dc&&y<=b; y++){
                int z = dc-x*1000-y*100;
                if(z > c) continue;
                int &d2 = dp[a-x+c3][b-y+c2][c-z+c1];
                d2 = max(d2,d+1);
            }
            answer = max(answer,d);
        }
    }
    cout << answer << endl;
}
0