#include "wombats.h"
#include <bits/stdc++.h>
#define debug
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
const int DIV = 40 ;
const int inf = 1e9+10 ;
const int MAXN = 5005 ;
const int MAXM = 205 ;
using namespace std ;
int N , M ;
int ini_bucket[MAXN] , end_bucket[MAXN];
int my_block[MAXN ] ;
int resp[MAXM][MAXM] ;
int opt[MAXM][MAXM] ;
int h[MAXN][MAXM] ;
int v[MAXN][MAXM] ;
int tree[130*4][MAXM][MAXM] ;
//Esta funcao recebe um pedaco do meu grid maior
//Com esse pedaco, ela calcula a dp
//Stora o resultado na matriz resp[MAXM][MAXM]
void calc(int n_menor , int n_maior )
{
if( n_menor == n_maior )
{
for(int i = 0 ; i < M ; i++ )
{
for(int j = 0 ; j < M ; j++ ) resp[i][j] = inf ;
resp[i][i] = 0 ;
}
return;
}
int dp[MAXN][MAXM] ;
for(int curr_c = 0; curr_c < M ; curr_c++ )
{
//Calculando a distancia de [n_menor][i] para [n_maior][j] , qualquer j
lp(i,n_menor, n_maior + 1)
lp(j,0,M) dp[i][j] = inf ;
dp[n_menor][ curr_c ] = 0 ;
for(int i = n_menor ; i <= n_maior ; i++ )
{
for(int j = 0 ; j < M ; j++ )
{
if( i > n_menor )
dp[i][j] = min( dp[i][j] , dp[i-1][j] + v[i-1][j] ) ;
if( j >= 1 )
dp[i][j] = min( dp[i][j] , dp[i][j-1] + h[i][j-1] ) ;
}
for(int j = M-2 ; j >= 0 ; j-- )
dp[i][j] = min( dp[i][j] , dp[i][j+1] + h[i][j] ) ;
}
for(int j = 0 ; j < M ; j++ )
resp[ curr_c ][j] = dp[n_maior][j] ;
}
}
int m(int l, int r) { return (l+r)>>1 ; }
void tres_colunas( int adj_left[][MAXM] ,int adj_right[][MAXM] )
{
/*debug("Printando adj_left\n") ;
for(int i = 0 ; i < M ; i++ , debug("\n") )
for(int j = 0 ; j < M ; j++ ) debug("%d " , adj_left[i][j] ) ;
debug("Printando adj_right\n") ;
for(int i = 0 ; i < M ; i++ , debug("\n") )
for(int j = 0 ; j < M ; j++ ) debug("%d " , adj_right[i][j] ) ;*/
//opt(i-1,j) <= opt(i,j) <= opt(i,j+1)
//opt(i,j+1) <= opt(i+1,j+1) <= opt(i+1,j+2)
for(int diff = M-1 ; diff >= 1-M ; diff -- )
{
for(int x = 0 ; x < M ; x++ )
{
int y = x + diff ;
if( y >= M || y < 0 ) continue ;
//debug("Calculating %d,%d\n", x , y ) ;
//calc opt[x][y]
int opt_min = 0 , opt_max = N-1 ;
if( x-1 >= 0 ) opt_min = opt[x-1][y] ;
if( y+1 < M ) opt_max = opt[x][y+1] ;
int opt_val = inf ;
for(int i = opt_min ; i <= opt_max ; i++ )
if( adj_left[x][i] + adj_right[i][y] < opt_val )
{
opt_val = adj_left[x][i] + adj_right[i][y] ;
resp[x][y] = opt_val ;
opt[x][y] = i ;
}
// debug("Opt = %d\n\n", opt[x][y] ) ;
}
}
/* debug("Printando resultado final\n") ;
for(int i = 0 ; i < M ; i++ , debug("\n") )
for(int j = 0 ; j < M ; j++ ) debug("%d " , resp[i][j] ) ;
debug("\n") ;*/
}
int adj_aux[MAXM][MAXM] ;
void merge(int pos, int l, int r)
{
int coluna_menor = end_bucket[ m(l,r) ] ;
int coluna_maior = ini_bucket[ m(l,r)+1 ] ;
calc(coluna_menor , coluna_maior ) ;
for(int i = 0 ; i < M ; i++ )
for(int j = 0 ; j < M ; j++ )
adj_aux[i][j] = resp[i][j] ;
tres_colunas( tree[pos*2] , adj_aux ) ;
for(int i = 0 ; i < M ; i++ )
for(int j = 0 ; j < M ; j++ )
adj_aux[i][j] = resp[i][j] ;
tres_colunas( adj_aux, tree[pos*2+1] ) ;
for(int i = 0 ; i < M ; i++ )
for(int j = 0 ; j < M ; j++ )
tree[pos][i][j] = resp[i][j] ;
}
void build_seg(int pos, int l, int r)
{
if( l == r )
{
calc( ini_bucket[l] , end_bucket[l] ) ;
for(int i = 0 ; i < M ; i++ )
for(int j = 0 ; j < M ; j++ )
tree[pos][i][j] = resp[i][j] ;
return ;
}
build_seg( pos*2,l, m(l,r) ) ;
build_seg( pos*2+1, m(l,r)+1 , r ) ;
merge(pos, l, r ) ;
}
void upd(int pos, int l, int r, int idx )
{
if( l == r )
{
calc( ini_bucket[l] , end_bucket[l] ) ;
for(int i = 0 ; i < M ; i++ )
for(int j = 0 ; j < M ; j++ )
tree[pos][i][j] = resp[i][j] ;
return ;
}
if( idx <= m(l,r) ) upd(pos*2,l,m(l,r),idx );
else upd(pos*2+1,m(l,r)+1, r, idx ) ;
merge(pos,l,r) ;
}
inline void print()
{
debug("Printing\n" ) ;
for(int i = 0 ; i < M ; i++ , debug("\n") )
for(int j = 0 ; j < M ; j++ ) debug("%d " , tree[1][i][j] ) ;
debug("\n") ;
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
N = R ;
M = C ;
for(int i = 0 ; i < N ; i++ )
for(int j = 0 ; j < M ; j++ )
{
h[i][j] = H[i][j] ;
v[i][j] = V[i][j] ;
}
ini_bucket[1] = 0 ;
for(int i = 0 , j = 0 , k = 1 ; i < N ; i++ , j++ )
{
if( j == DIV )
{
k++ ;
j = 0 ;
ini_bucket[k] = i ;
}
my_block[i] = k ;
end_bucket[k] = i ;
}
build_seg(1,1, my_block[N-1] ) ;
for(int i = 0 ; i < M ; i++, debug("\n") )
for(int j = 0 ; j < M ; j++ ) debug("%d " , resp[i][j] ) ;
}
void changeH(int P, int Q, int W)
{
h[P][Q] = W ;
upd( 1 , 1 , my_block[ N-1 ] , my_block[P] ) ;
//print() ;
}
void changeV(int P, int Q, int W)
{
v[P][Q] = W ;
upd( 1 , 1, my_block[N-1] , my_block[P] ) ;
//print() ;
}
int escape(int V1, int V2)
{
return tree[1][V1][V2] ;
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
wombats.cpp: In function 'void print()':
wombats.cpp:215:23: warning: statement has no effect [-Wunused-value]
debug("Printing\n" ) ;
^
wombats.cpp:216:42: warning: right operand of comma operator has no effect [-Wunused-value]
for(int i = 0 ; i < M ; i++ , debug("\n") )
^
wombats.cpp:217:59: warning: left operand of comma operator has no effect [-Wunused-value]
for(int j = 0 ; j < M ; j++ ) debug("%d " , tree[1][i][j] ) ;
^
wombats.cpp:218:14: warning: statement has no effect [-Wunused-value]
debug("\n") ;
^
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:254:41: warning: right operand of comma operator has no effect [-Wunused-value]
for(int i = 0 ; i < M ; i++, debug("\n") )
^
wombats.cpp:255:56: warning: left operand of comma operator has no effect [-Wunused-value]
for(int j = 0 ; j < M ; j++ ) debug("%d " , resp[i][j] ) ;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
17400 KB |
Output is correct |
| 2 |
Incorrect |
86 ms |
17656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
504 KB |
Output is correct |
| 5 |
Correct |
5 ms |
504 KB |
Output is correct |
| 6 |
Correct |
5 ms |
504 KB |
Output is correct |
| 7 |
Correct |
6 ms |
504 KB |
Output is correct |
| 8 |
Correct |
5 ms |
504 KB |
Output is correct |
| 9 |
Correct |
5 ms |
504 KB |
Output is correct |
| 10 |
Correct |
5 ms |
504 KB |
Output is correct |
| 11 |
Correct |
97 ms |
1528 KB |
Output is correct |
| 12 |
Correct |
5 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
1400 KB |
Output is correct |
| 2 |
Correct |
452 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
434 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
431 ms |
1536 KB |
Output is correct |
| 5 |
Incorrect |
460 ms |
1656 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
21496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
328 ms |
1508 KB |
Output is correct |
| 2 |
Correct |
456 ms |
1564 KB |
Output is correct |
| 3 |
Correct |
431 ms |
1556 KB |
Output is correct |
| 4 |
Correct |
433 ms |
1528 KB |
Output is correct |
| 5 |
Incorrect |
469 ms |
1528 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
319 ms |
1400 KB |
Output is correct |
| 2 |
Correct |
448 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
435 ms |
1592 KB |
Output is correct |
| 4 |
Correct |
429 ms |
1532 KB |
Output is correct |
| 5 |
Incorrect |
458 ms |
1528 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
