oj.uz

Submission #204010

# Submission time Handle Problem Language Result Execution time Memory
204010 2020-02-23T17:10:48 Z CaroLinda Wombats (IOI13_wombats) C++14
12 / 100
 309 ms 21496 KB 
#include "wombats.h"
#include <bits/stdc++.h>

#define debug 
#define lp(i,a,b) for(int i = a ; i < b ; i++ )

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 )
{

	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 >= 1 )
					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] )
{

	//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 >= 0 ; diff -- )
	{

		for(int x = 0 ; x < N ; x++ )
		{
			int y = x+ diff ;
			if( y >= M ) continue ;

			//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 < N ) 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 ;
				}

		}

	}

}

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 ) return (void)( calc(ini_bucket[l] , end_bucket[l]) ) ;

	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) ;

}

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 == 40 ) 
		{
			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 " , tree[1][i][j] ) ;

}

void changeH(int P, int Q, int W) 
{
    h[P][Q] = W ;
    upd( 1 , 1 , my_block[ N-1 ] , my_block[P] ) ;
}

void changeV(int P, int Q, int W) 
{
    v[P][Q] = W ;
    upd( 1 , 1,  my_block[N-1] , my_block[P] ) ;
}

int escape(int V1, int V2) 
{
    return resp[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 init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:201:41: warning: right operand of comma operator has no effect [-Wunused-value]
  for(int i = 0 ; i < M ; i++, debug("\n") )
                                         ^
wombats.cpp:202: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] ) ;
                                                           ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 17400 KB Output is correct
2 Incorrect 63 ms 17400 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 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 5 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 99 ms 1580 KB Output is correct
12 Correct 5 ms 504 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 1504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 1404 KB Output isn't correct
2 Halted 0 ms 0 KB -