結果

問題 No.2366 登校
ユーザー 👑 hitonanodehitonanode
提出日時 2023-06-30 23:01:20
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,671 bytes
コンパイル時間 935 ms
コンパイル使用メモリ 92,416 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2023-09-22 17:38:59
合計ジャッジ時間 2,019 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 7 ms
4,884 KB
testcase_13 AC 3 ms
4,380 KB
testcase_14 AC 4 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 6 ms
4,380 KB
testcase_18 AC 5 ms
4,376 KB
testcase_19 AC 7 ms
4,836 KB
testcase_20 AC 3 ms
4,380 KB
testcase_21 AC 3 ms
4,380 KB
testcase_22 AC 7 ms
4,856 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 4 ms
4,376 KB
testcase_25 WA -
testcase_26 AC 26 ms
11,136 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
using lint = long long;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

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

    int N, M, K, T;
    cin >> N >> M >> K >> T;
    const int req_red = (N - 1) + (M - 1) - T;

    if (T >= (N - 1) + (M - 1)) {
        puts("0");
        return 0;
    }

    vector<int> C(N * M);
    vector<int> D(N * M);

    auto fij = [&](int i, int j) { return i * M + j; };
    auto f = [&](int i, int j, int t) { return (i * M + j) * (req_red + 1) + t; };

    REP(k, K) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a, --b;
        C.at(fij(a, b)) = c - 1;
        D.at(fij(a, b)) = d;
    }


    const int sz = N * M * (req_red + 1);
    constexpr lint inf = 1LL << 60;
    vector<lint> dp(sz, inf);
    dp.at(f(0, 0, 0)) = 0;

    REP(t, req_red + 1) {
        REP(i, N) REP(j, M) {
            for (auto [di, dj] : grid_dxs) {
                int ni = i + di, nj = j + dj;
                if (ni < 0 or ni >= N or nj < 0 or nj >= M) continue;
                chmin(dp.at(f(ni, nj, t)), dp.at(f(i, j, t)));
            }
        }
        REP(i, N) REP(j, M) {
            if (C.at(fij(i, j)) > 0) chmin(dp.at(f(i, j, min(t + C.at(fij(i, j)), req_red))), dp.at(f(i, j, t)) + D.at(fij(i, j)));
        }
    }

    lint ret = dp.at(f(N - 1, M - 1, req_red));
    cout << (ret < inf ? ret : -1) << endl;
}
0