結果

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

ソースコード

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; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {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