| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 608726 | MohamedFaresNebili | 웜뱃 (IOI13_wombats) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int oo = 1000 * 1000 * 1000 + 7;
int R, C, H[5000][200], K[5000][200];
void init(int r, int c, int h[5000][200], int v[5000][200]) {
R = r, C = c;
for(int l = 0; l < R; l++)
for(int i = 0; i < C; i++)
H[l][i] = h[l][i],
K[l][i] = v[l][i];
}
void changeH(int P, int Q, int W) { H[P][Q] = W; }
void changeV(int P, int Q, int W) { K[P][Q] = W; }
using pi = pair<int, pair<int, int>>;
int escape(int V1, int V2) {
priority_queue<pi, vector<pi>, greater<pi>> pq;
pq.push({0, {0, V1}}); vector<vector<int>> D;
D = vector<vector<int>> (R, vector<int>(C, oo));
D[0][V1] = 0;
while(!pq.empty()) {
int U = pq.top().ss.ff, V = pq.top().ss.ss;
int W = pq.top().ff; pq.pop();
if(W != D[U][V]) continue;
if(V < C - 1) {
if(D[U][V + 1] > D[U][V] + H[U][V]) {
D[U][V + 1] = D[U][V] + H[U][V];
pq.push({D[U][V + 1], {U, V + 1}});
}
}
if(V > 0) {
if(D[U][V - 1] > D[U][V] + H[U][V - 1]) {
D[U][V - 1] = D[U][V] + H[U][V - 1];
pq.push({D[U][V - 1], {U, V - 1}});
}
}
if(U < R - 1) {
if(D[U + 1][V] > D[U][V] + K[U][V]) {
D[U + 1][V] = D[U][V] + K[U][V];
pq.push({D[U + 1][V], {U + 1, V}});
}
}
}
return D[R - 1][V2];
}