| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 411635 | albertolg101 | Wombats (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "wombats.h"
#define int long long
using namespace std;
using pii = pair<int, int>;
const int INF = 1e16;
int n, m;
vector<vector<int>> h(5001, vector<int> (201)), v = h, dp = h;
bool sol = false;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R, m = C;
for(int i = 0 ; i < R ; i++)
{
for(int j = 0 ; j < C - 1 ; j++)
{
h[i][j] = H[i][j];
}
}
for(int i = 0 ; i < R - 1 ; i++)
{
for(int j = 0 ; j < C ; j++)
{
v[i][j] = V[i][j];
}
}
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
sol = false;
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
sol = false;
}
int escape(int V1, int V2)
{
for(int i = 0 ; i < m ; i++)
{
dp[n-1][i] = INF;
}
dp[n-1][V2] = 0;
for(int i = n - 1 ; i >= 0 ; i--)
{
set<pii> s;
for(int j = 0 ; j < m ; j++)
s.insert({dp[i][j], j});
while(s.size())
{
int j, dist, dist2;
tie(dist, j) = *s.begin();
dist2 = dist;
s.erase(s.begin());
if(dp[i][j] < dist)
continue;
for(int k = j + 1 ; k < m ; k++)
{
if(dp[i][k] > dist + h[i][k-1])
{
dp[i][k] = dist + h[i][k-1];
dist += h[i][k-1];
}
else
break;
}
for(int k = j - 1 ; k >= 0 ; k--)
{
dist2 += h[i][k];
if(dp[i][k] > dist2 + h[i][k])
{
dp[i][k] = dist2 + h[i][k];
}
else
break;
}
}
for(int j = 0 ; j < m and i != 0; j++)
{
dp[i-1][j] = dp[i][j] + v[i-1][j];
}
}
/*
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < m - 1; j++)
{
cout << h[i][j] << ' ' ;
}
cout << endl ;
}
cout << endl ;
for(int i = 0 ; i < n - 1 ; i++)
{
for(int j = 0 ; j < m ; j++)
{
cout << v[i][j] << ' ' ;
}
cout << endl ;
}
cout << endl ;
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < m ; j++)
{
cout << dp[i][j] << ' ' ;
}
cout << endl;
}
*/
return dp[0][V1];
}
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
static int H[5000][200];
static int V[5000][200];
int main() {
int R, C, E, P, Q, W, V1, V2, event, i, j;
int res;
FILE *f = fopen("wombats.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d", &R, &C);
for (i = 0; i < R; ++i)
for (j = 0; j < C-1; ++j)
res = fscanf(f, "%d", &H[i][j]);
for (i = 0; i < R-1; ++i)
for (j = 0; j < C; ++j)
res = fscanf(f, "%d", &V[i][j]);
init(R, C, H, V);
res = fscanf(f, "%d", &E);
for (i = 0; i < E; i++) {
res = fscanf(f, "%d", &event);
if (event == 1) {
res = fscanf(f, "%d%d%d", &P, &Q, &W);
changeH(P, Q, W);
} else if (event == 2) {
res = fscanf(f, "%d%d%d", &P, &Q, &W);
changeV(P, Q, W);
} else if (event == 3) {
res = fscanf(f, "%d%d", &V1, &V2);
printf("%d\n", escape(V1, V2));
} else
fail("Invalid event type.");
}
fclose(f);
return 0;
}