不便な橋 [技術室奥プログラミングコンテスト#4 Day1 F]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_f

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6663997

ある島からある島へ行くのに、M通りの方法があるが、その中で最も早く到着できる経路で進めばいい。
これはどの移動でもそうであり、つまり、貪欲法で解ける。
ゲートが開く時刻を求める計算が少し大変かもしれない。

int N, M, A[505][505], B[505][505];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) rep(j, 0, M) cin >> A[i][j];
    rep(i, 0, N) rep(j, 0, M) cin >> B[i][j];

    int t = 0;
    rep(i, 0, N) {
        int opt = inf;
        rep(j, 0, M) {
            int t2 = t;
            if (0 < t2 % A[i][j]) t2 += (A[i][j] - (t2 % A[i][j]));
            chmin(opt, t2 + B[i][j]);
        }
        t = opt;
    }
    cout << t << endl;
}