/**
____ ____ ____ __________________ ____ ____ ____
||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;
/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}*/
typedef pair <long long, int> pli;
int d[maxn];
int c, r;
int h[maxn][maxn2];
int v[maxn][maxn2];
int dp[maxn][maxn2];
void dijkstra(int node)
{
for(int i = 0; i < c; i++)
d[i] = 1e9;
d[node] = 0;
for(int j = 0; j < r; j++)
{
set <int> q;
for(int i = 0; i < c; i++)
if(d[i] != 1e9)
q.emplace(i);
while(q.size())
{
int e = *q.begin();
q.erase(q.begin());
if(e + 1 < c)
if(d[e + 1] > d[e] + h[j][e])
{
d[e + 1] = d[e] + h[j][e];
q.emplace(e + 1);
}
if(e >= 1)
if(d[e - 1] > d[e] + h[j][e - 1])
{
d[e - 1] = d[e] + h[j][e - 1];
q.emplace(e - 1);
}
}
if(j + 1 < r)
for(int i = 0; i < c; i++)
d[i] += v[j][i];
}
for(int i = 0; i < c; i++)
dp[node][i] = d[i];
}
int dp2[maxn][maxn][maxr];
void calc(int k)
{
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
dp2[k][j][i] = 1e9;
dp2[k][k][0] = 0;
for(int i = 1; i < c; i++)
dp2[k][i][0] = min(dp2[k][i][0] , dp2[k][i - 1][0] + h[0][i - 1]);
for(int i = c - 2; i > -1; i--)
dp2[k][i][0] = min(dp2[k][i][0] , dp2[k][i + 1][0] + h[0][i]);
for(int i = 1; i < r; i++)
{
for(int j = 0; j < c; j++)
dp2[k][j][i] = dp[k][j][i - 1] + v[i - 1][j];
for(int ii = 1; ii < c; ii++)
dp2[k][ii][i] = min(dp2[k][ii][i] , dp2[k][ii - 1][i] + h[i][ii - 1]);
for(int ii = c - 2; ii > -1; ii--)
dp2[k][ii][i] = min(dp2[k][ii][i] , dp2[k][ii + 1][i] + h[i][ii]);
}
}
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 dp2[V1][V2][r - 1];
}
/**int main()
{
#ifdef ONLINE_JUDGE /// promeni
freopen("input.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//startT = std::chrono::high_resolution_clock::now();
return 0;
}*/
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
wombats.cpp:97:21: error: 'maxr' was not declared in this scope; did you mean 'maxn'?
97 | int dp2[maxn][maxn][maxr];
| ^~~~
| maxn
wombats.cpp: In function 'void calc(int)':
wombats.cpp:104:13: error: 'dp2' was not declared in this scope; did you mean 'dp'?
104 | dp2[k][j][i] = 1e9;
| ^~~
| dp
wombats.cpp:105:5: error: 'dp2' was not declared in this scope; did you mean 'dp'?
105 | dp2[k][k][0] = 0;
| ^~~
| dp
wombats.cpp:116:36: error: invalid types 'int[int]' for array subscript
116 | dp2[k][j][i] = dp[k][j][i - 1] + v[i - 1][j];
| ^
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:143:9: error: 'calc_dp' was not declared in this scope; did you mean 'calc'?
143 | calc_dp(i);
| ^~~~~~~
| calc
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:152:9: error: 'calc_dp' was not declared in this scope; did you mean 'calc'?
152 | calc_dp(i);
| ^~~~~~~
| calc
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:159:9: error: 'calc_dp' was not declared in this scope; did you mean 'calc'?
159 | calc_dp(i);
| ^~~~~~~
| calc
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:165:12: error: 'dp2' was not declared in this scope; did you mean 'dp'?
165 | return dp2[V1][V2][r - 1];
| ^~~
| dp
