# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
962286 | Ice_man | 웜뱃 (IOI13_wombats) | C++14 | 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.
/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
//#include"wombats.h"
#include <set>
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cstdio>
#define maxn 5005
#define maxn2 205
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")
using namespace std;
int c, r;
int h[maxn][maxn2];
int v[maxn][maxn2];
int dp[5001][5001][201];
void calc_row(int i , int k)
{
for(int j = 1; j < c; j++)
dp[i][j][k] = min(dp[i][j][k] , dp[i][j - 1][k] + h[k][j - 1]);
for(int j = c - 2; j > -1; j--)
dp[i][j][k] = min(dp[i][j][k] , dp[i][j + 1][k] + h[j][j]);
}
void calc_dp(int k)
{
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
dp[k][j][i] = 1e9;
dp[k][k][0] = 0;
calc_row(k , 0);
for(int i = 1; i < r; i++)
{
for(int j = 0; j < c; j++)
dp[k][j][i] = dp[k][j][i - 1] + v[i - 1][j];
calc_row(k , i);
}
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
r = R;
c = C;
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
{
if(j + 1 < c)
h[i][j] = H[i][j];
if(i + 1 < r)
v[i][j] = V[i][j];
}
for(int i = 0; i < c; i++)
calc_dp(i);
}
void changeH(int P , int Q , int W)
{
h[P][Q] = W;
for(int i = 0; i < c; i++)
calc_dp(i);
}
void changeV(int P , int Q , int W)
{
v[P][Q] = W;
for(int i = 0; i < c; i++)
calc_dp(i);
}
int escape(int V1 , int V2)
{
return dp[V1][V2][r - 1];
}