結果
問題 | No.2855 Move on Grid |
ユーザー |
|
提出日時 | 2023-10-25 12:58:42 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 187 ms / 3,000 ms |
コード長 | 3,994 bytes |
コンパイル時間 | 1,608 ms |
コンパイル使用メモリ | 144,776 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 13:01:14 |
合計ジャッジ時間 | 7,629 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
/*{{{ author: ryota2357 */#include <algorithm>#include <cassert>#include <cmath>#include <deque>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <tuple>#include <utility>#include <vector>namespace ryota2357{template <class T1, class T2>inline std::istream& operator>>(std::istream& is, std::pair<T1, T2>& P) noexcept {return is >> P.first >> P.second;}template <class T>inline std::istream& operator>>(std::istream& is, std::vector<T>& V) noexcept {for (auto& v : V) is >> v;return is;}template <class T>inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& V) noexcept {const auto n = V.size() - 1;for (int i = 0; i < n; ++i) os << V[i] << ' ';return os << V.back();}inline void IN(void) noexcept { return; }template <class T, class... U>inline void IN(T& t, U&... u) noexcept {std::cin >> t;IN(u...);}template <class T>inline void OUT(const T& x) noexcept { std::cout << x << '\n'; }template <class T>inline bool chmax(T& a, const T& b) noexcept { return a < b ? a = b, true : false; }template <class T>inline bool chmin(T& a, const T& b) noexcept { return a > b ? a = b, true : false; }template <class T = int>inline T read(void) {T ret = 0;char c = getchar();while ((c < '0' || '9' < c) && c != '-') c = getchar();const bool f = (c == '-') && (c = getchar());while ('0' <= c && c <= '9') {ret = 10 * ret + c - '0';c = getchar();}return f ? -ret : ret;}template <class T>inline T ceil_div(const T& a, const T& b) {assert(b != 0);return (a + (b - 1)) / b;}template <class T>inline T max(const std::vector<T>& v) { return *max_element(v.begin(), v.end()); }template <class T>inline T min(const std::vector<T>& v) { return *min_element(v.begin(), v.end()); }template <class F>inline constexpr decltype(auto) recursive(F&& f) {return [f = std::forward<F>(f)](auto&&... args) {return f(f, std::forward<decltype(args)>(args)...);};}} // namespace ryota2357using ll = long long;using pint = std::pair<int, int>;#define rep(i, a, b) for (ll i = (a); i < ll(b); ++i)#define repr(i, a, b) for (ll i = (a); i >= ll(b); --i)#define each(x, v) for (auto& x : v)#define All(x) (x).begin(), (x).end()#define AllR(x) (x).rbegin(), (x).rend()#define Sort(x) (sort((x).begin(), (x).end()))#define SortR(x) (sort((x).rbegin(), (x).rend()))#define Unique(x) (x.erase(unique((x).begin(), (x).end()), (x).end()))#define Fill(v, n) (fill((v), (v) + sizeof(v) / sizeof(*(v)), (v)))#define INF (1073741823)#define INFL (2305843009213693951ll)using namespace std;using namespace ryota2357;/*}}}*/int main() {int n, m, k; IN(n, m, k);vector a(n, vector<int>(m)); IN(a);int l = 0, r = 1000000001;while (r - l > 1) {int mid = (l + r) / 2;deque<tuple<int, int, int>> que;vector cost(n, vector<int>(m, -1));que.push_front({0, 0, (a[0][0] < mid ? 1 : 0)});const int dx[] = {1, 0, -1, 0};const int dy[] = {0, 1, 0, -1};while (que.size()) {auto [x, y, c] = que.front(); que.pop_front();if (cost[y][x] != -1) {continue;}cost[y][x] = c;rep(i, 0, 4) {int nx = x + dx[i];int ny = y + dy[i];if (nx < 0 || nx >= m || ny < 0 || ny >= n) {continue;}if (cost[ny][nx] != -1) {continue;}if (a[ny][nx] < mid) {que.push_back({nx, ny, c + 1});} else {que.push_front({nx, ny, c});}}}if (cost[n-1][m-1] <= k) {l = mid;} else {r = mid;}}OUT(l);return 0;}