結果
問題 | No.2855 Move on Grid |
ユーザー |
👑 ![]() |
提出日時 | 2024-08-25 13:44:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 138 ms / 3,000 ms |
コード長 | 1,721 bytes |
コンパイル時間 | 3,072 ms |
コンパイル使用メモリ | 257,176 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 13:44:39 |
合計ジャッジ時間 | 7,667 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 998244353;// constexpr int MOD = 1000000007;constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U>inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U>inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;int main() {int n, m, k; cin >> n >> m >> k;vector a(n, vector(m, 0));for (vector<int>& a_i : a) for (int& a_ij : a_i) cin >> a_ij;int ans = 1;for (int ub = 1000000001; ub - ans > 1;) {const int mid = midpoint(ans, ub);vector dist(n, vector(m, INF));dist[0][0] = (a[0][0] < mid ? 1 : 0);for (deque<pair<int, int>> que({{0, 0}}); !que.empty();) {const auto [y, x] = que.front();que.pop_front();REP(k, 4) {const int ny = y + DY4[k], nx = x + DX4[k];if (0 <= ny && ny < n && 0 <= nx && nx < m && chmin(dist[ny][nx], dist[y][x] + (a[ny][nx] < mid ? 1 : 0))) {if (a[ny][nx] < mid) {que.emplace_back(ny, nx);} else {que.emplace_front(ny, nx);}}}}(dist[n - 1][m - 1] <= k ? ans : ub) = mid;}cout << ans << '\n';return 0;}