結果
問題 | No.2855 Move on Grid |
ユーザー |
👑 ![]() |
提出日時 | 2024-08-25 14:20:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,865 bytes |
コンパイル時間 | 4,567 ms |
コンパイル使用メモリ | 248,476 KB |
実行使用メモリ | 108,012 KB |
最終ジャッジ日時 | 2024-08-25 14:20:46 |
合計ジャッジ時間 | 11,376 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 TLE * 1 -- * 33 |
ソースコード
#define ATCODER#define _USE_MATH_DEFINES#include <stdio.h>#include <iostream>#include <fstream>#include <algorithm>#include <vector>#include <string>#include <cassert>#include <numeric>#include <unordered_map>#include <unordered_set>#include <queue>#include <math.h>#include <climits>#include <set>#include <map>#include <list>#include <random>#include <iterator>#include <bitset>#include <chrono>#include <type_traits>using namespace std;using ll = long long;using ld = long double;using pll = pair<ll, ll>;using pdd = pair<ld, ld>;#define FOR(i, a, b) for (ll i = (a); i < (b); i++)#define REP(i, n) for (ll i = 0; i < (n); i++)#define ROF(i, a, b) for (ll i = (b - 1); i >= (a); i--)#define PER(i, n) for (ll i = n - 1; i >= 0; i--)#define VL vector<ll>#define VVL vector<vector<ll>>#define VP vector<pair<ll, ll>>#define LPQ(T) priority_queue<T, vector<T>, greater<T>>#define all(i) begin(i), end(i)#define SORT(i) sort(all(i))#define EXISTBIT(x, i) (((x >> i) & 1) != 0)#define CHMAX(n, v) n = n < v ? v : n#define CHMIN(n, v) n = n > v ? v : n#define MP(a, b) make_pair(a, b)#define DET2(x1, y1, x2, y2) (x1) * (y2) - (x2) * (y1)#define DET3(x1, y1, z1, x2, y2, z2, x3, y3, z3) (x1) * (y2) * (z3) + (x2) * (y3) * (z1) + (x3) * (y1) * (z2) - (z1) * (y2) * (x3) - (z2) * (y3) *(x1) - (z3) * (y1) * (x2)#define INC(a) \for (auto &v : a) \v++;#define DEC(a) \for (auto &v : a) \v--;#define SQU(x) (x) * (x)#ifdef ATCODER#include <atcoder/all>using namespace atcoder;using mint = modint1000000007;using mint2 = modint998244353;#endiftemplate <typename T = ll>vector<T> read(size_t n){vector<T> ts(n);for (size_t i = 0; i < n; i++)cin >> ts[i];return ts;}template <typename TV, const ll N>void read_tuple_impl(TV &) {}template <typename TV, const ll N, typename Head, typename... Tail>void read_tuple_impl(TV &ts){get<N>(ts).emplace_back(*(istream_iterator<Head>(cin)));read_tuple_impl<TV, N + 1, Tail...>(ts);}template <typename... Ts>decltype(auto) read_tuple(size_t n){tuple<vector<Ts>...> ts;for (size_t i = 0; i < n; i++)read_tuple_impl<decltype(ts), 0, Ts...>(ts);return ts;}using val = mint;using val2 = mint2;using func = ll;val op(val a, val b){return a*b;}val e() { return 1; }val2 op2(val2 a, val2 b){return a*b;}val2 e2() { return 1; }val mp(func f, val a){return a + f;}func comp(func f, func g){return f + g;}func id() { return 0; }ll di[4] = {1, 0, -1, 0};ll dj[4] = {0, 1, 0, -1};ll si[4] = {0, 3, 3, 0};ll sj[4] = {0, 0, 3, 3};// ll di[4] = { -1,-1,1,1 };// ll dj[4] = { -1,1,-1,1 };ll di8[8] = {0, -1, -1, -1, 0, 1, 1, 1};ll dj8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};void solve(){ll h,w,k;cin>>h>>w>>k;VVL a(h);REP(i,h)a[i]=read(w);k=min(k,h+w);priority_queue<tuple<ll,ll,ll,ll>> que;vector dist(h,vector(w,vector<ll>(k+1)));dist[0][0][0]=a[0][0];que.emplace(a[0][0],0,0,0);if(k){dist[0][0][1]=1000000000;que.emplace(1000000000,0,0,1);}while(!que.empty()){auto [d,x,y,kk]=que.top();que.pop();if(dist[x][y][kk] > d)continue;if(kk>k)continue;if(kk < k && dist[x][y][kk+1] < d){dist[x][y][kk+1]=d;que.emplace(d,x,y,kk+1);}REP(dir,4){ll nx=x+di[dir];ll ny=y+dj[dir];if(nx<0||ny<0||nx>=h||ny>=w)continue;ll md=min(d,a[nx][ny]);if(dist[nx][ny][kk+0] < md){dist[nx][ny][kk+0]=md;que.emplace(md,nx,ny,kk);}if(kk < k && dist[nx][ny][kk+1] < d){dist[nx][ny][kk+1]=d;que.emplace(d,nx,ny,kk+1);}}}ll ans=0;REP(i,k+1){CHMAX(ans,dist[h-1][w-1][i]);}cout<<ans<<endl;return;}int main(){ll t = 1;//cin >> t;while (t--){solve();}return 0;}