結果

問題 No.158 奇妙なお使い
コンテスト
ユーザー kimiyuki
提出日時 2016-10-06 04:19:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 76 ms / 5,000 ms
コード長 1,987 bytes
コンパイル時間 935 ms
コンパイル使用メモリ 92,836 KB
実行使用メモリ 50,688 KB
最終ジャッジ日時 2024-06-29 19:31:32
合計ジャッジ時間 3,874 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> bool setmax(T & a, T const & b) { if (a < b) { a = b; return true; } else return false; }
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
const int N = 10000, N0 = 1000, N1 = 100, N2 = 1;
int main() {
    int a0, a1, a2; cin >> a0 >> a1 >> a2;
    int db;         cin >> db;
    int b0, b1, b2; cin >> b0 >> b1 >> b2;
    int dc;         cin >> dc;
    int c0, c1, c2; cin >> c0 >> c1 >> c2;
    vector<vector<vector<int> > > dp = vectors(-1, N/N0+1, N/N1+1, N/N2+1);
    repeat (i,N/N0+1) repeat (j,N/N1+1) repeat (k,N/N2+1) dp[i][j][k] = -1;
    dp[a0][a1][a2] = 0;
    int ans = -1;
    while (true) {
        bool modified = false;
        repeat_reverse (i,N/N0+1) repeat_reverse (j,N/N1+1) repeat_reverse (k,N/N2+1) if (dp[i][j][k] != -1) {
            setmax(ans, dp[i][j][k]);
            auto foo = [&](int de, int e0, int e1, int e2) {
                int di = min(i, de / N0); de -= N0 * di;
                int dj = min(j, de / N1); de -= N1 * dj;
                int dk = min(k, de / N2); de -= N2 * dk;
                if (de == 0) {
                    if (setmax(dp[i-di+e0][j-dj+e1][k-dk+e2], dp[i][j][k] + 1)) {
                        modified = true;
                    }
                }
            };
            foo(db, b0, b1, b2);
            foo(dc, c0, c1, c2);
        }
        if (not modified) break;
    }
    cout << ans << endl;
    return 0;
}
0