結果
| 問題 | No.2366 登校 |
| ユーザー |
 ebi_fly
|
| 提出日時 | 2023-06-30 22:51:30 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 696 ms / 4,000 ms |
| コード長 | 5,616 bytes |
| コンパイル時間 | 1,711 ms |
| コンパイル使用メモリ | 156,212 KB |
| 最終ジャッジ日時 | 2025-02-15 04:26:02 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <chrono>#include <climits>#include <cmath>#include <complex>#include <cstddef>#include <cstdint>#include <cstdlib>#include <cstring>#include <functional>#include <iomanip>#include <iostream>#include <limits>#include <map>#include <memory>#include <numeric>#include <optional>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>/* macro */#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)#define rrep(i, a, n) for (int i = ((int)(n)-1); i >= (int)(a); i--)#define Rep(i, a, n) for (i64 i = (i64)(a); i < (i64)(n); i++)#define RRep(i, a, n) for (i64 i = ((i64)(n)-i64(1)); i >= (i64)(a); i--)#define all(v) (v).begin(), (v).end()#define rall(v) (v).rbegin(), (v).rend()/* macro end *//* template */namespace ebi {#ifdef LOCAL#define debug(...) \std::cerr << "LINE: " << __LINE__ << " [" << #__VA_ARGS__ << "]:", \debug_out(__VA_ARGS__)#else#define debug(...)#endifvoid debug_out() {std::cerr << std::endl;}template <typename Head, typename... Tail> void debug_out(Head h, Tail... t) {std::cerr << " " << h;if (sizeof...(t) > 0) std::cerr << " :";debug_out(t...);}template <typename T1, typename T2>std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &pa) {return os << pa.first << " " << pa.second;}template <typename T1, typename T2>std::istream &operator>>(std::istream &os, std::pair<T1, T2> &pa) {return os >> pa.first >> pa.second;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");return os;}template <typename T>std::istream &operator>>(std::istream &os, std::vector<T> &vec) {for (T &e : vec) std::cin >> e;return os;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::optional<T> &opt) {if (opt) {os << opt.value();} else {os << "invalid value";}return os;}using std::size_t;using i32 = std::int32_t;using u32 = std::uint32_t;using i64 = std::int64_t;using u64 = std::uint64_t;using i128 = __int128_t;using u128 = __uint128_t;template <class T> inline bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;}template <class T> inline bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;}template <class T> T pow(T x, i64 n) {T res = 1;while (n > 0) {if (n & 1) res = res * x;x = x * x;n >>= 1;}return res;}template <class T> struct Edge {int to;T cost;Edge(int _to, T _cost = 1) : to(_to), cost(_cost) {}};template <class T> struct Graph : std::vector<std::vector<Edge<T>>> {using std::vector<std::vector<Edge<T>>>::vector;void add_edge(int u, int v, T w, bool directed = false) {(*this)[u].emplace_back(v, w);if (directed) return;(*this)[v].emplace_back(u, w);}};struct graph : std::vector<std::vector<int>> {using std::vector<std::vector<int>>::vector;void add_edge(int u, int v, bool directed = false) {(*this)[u].emplace_back(v);if (directed) return;(*this)[v].emplace_back(u);}};constexpr i64 LNF = std::numeric_limits<i64>::max() / 4;constexpr int INF = std::numeric_limits<int>::max() / 2;const std::vector<int> dy = {1, 0, -1, 0, 1, 1, -1, -1};const std::vector<int> dx = {0, 1, 0, -1, 1, -1, 1, -1};} // namespace ebinamespace ebi {void main_() {int n,m,k;i64 t;std::cin >> n >> m >> k >> t;std::vector magic(n, std::vector<std::pair<i64,i64>>(m, {-1, -1}));rep(i,0,k) {int a,b;i64 c,d;std::cin >> a >> b >> c >> d;a--; b--;magic[a][b] = {c - 1, d};}if(n + m <= t) {std::cout << 0 << '\n';return;}int zero = 200;int max = 600;std::vector dp(n, std::vector(m, std::vector<i64>(max, LNF)));dp[0][0][zero] = 0;using P = std::tuple<i64,int,int,int>;std::priority_queue<P, std::vector<P>, std::greater<P>> que;que.push({0,0,0,zero});while(!que.empty()) {auto [ret, y, x, i] = que.top();que.pop();if(dp[y][x][i] < ret) continue;rep(j,0,4) {int ny = y + dy[j];int nx = x + dx[j];if(0 <= ny && ny < n && 0 <= nx && nx < m && i + 1 < max) {if(chmin(dp[ny][nx][i+1], dp[y][x][i])) {que.push({dp[ny][nx][i+1], ny, nx, i+1});}}}if(magic[y][x].first != -1) {auto [c, d] = magic[y][x];int nxt = std::max(i64(0), i - c);if(chmin(dp[y][x][nxt], dp[y][x][i] + d)) {que.push({dp[y][x][nxt], y, x, nxt});}}}i64 ans = LNF;rep(i,0,zero + t + 1) {chmin(ans, dp[n-1][m-1][i]);}if(ans == LNF) ans = -1;std::cout << ans << '\n';}} // namespace ebiint main() {std::cout << std::fixed << std::setprecision(15);std::cin.tie(nullptr);std::ios::sync_with_stdio(false);int t = 1;// std::cin >> t;while (t--) {ebi::main_();}return 0;}