結果

問題 No.2366 登校
ユーザー hitonanodehitonanode
提出日時 2023-07-01 01:30:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,768 bytes
コンパイル時間 939 ms
コンパイル使用メモリ 92,520 KB
実行使用メモリ 11,168 KB
最終ジャッジ日時 2024-07-07 22:05:59
合計ジャッジ時間 1,456 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 3
権限があれば一括ダウンロードができます

ソースコード

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 IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }

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 - 1) REP(j, M) chmin(dp.at(f(i + 1, j, t)), dp.at(f(i, j, t)) + 0);
        REP(i, N) REP(j, M - 1) chmin(dp.at(f(i, j + 1, t)), dp.at(f(i, j, t)) + 0);
        IFOR(i, 1, N) IREP(j, M) chmin(dp.at(f(i - 1, j, t)), dp.at(f(i, j, t)) + 2);
        IREP(i, N) IFOR(j, 1, M) chmin(dp.at(f(i, j - 1, t)), dp.at(f(i, j, t)) + 2);

        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