oj.uz

Submission #204013

# Submission time Handle Problem Language Result Execution time Memory
204013 2020-02-23T18:22:09 Z CaroLinda Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 28148 KB 
#include "wombats.h"
#include <bits/stdc++.h>

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

const int DIV = 5000 ;
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] )
{

	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 ;

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

		}

	}

}

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

}

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

}

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 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;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16376 KB Output is correct
2 Correct 38 ms 16248 KB Output is correct
3 Correct 126 ms 17912 KB Output is correct
4 Correct 40 ms 16248 KB Output is correct
5 Correct 38 ms 16248 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct

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 632 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 95 ms 1528 KB Output is correct
12 Correct 5 ms 504 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 1016 KB Output is correct
2 Correct 903 ms 1016 KB Output is correct
3 Correct 933 ms 1016 KB Output is correct
4 Correct 936 ms 1016 KB Output is correct
5 Correct 914 ms 1016 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 4594 ms 1052 KB Output is correct
10 Correct 5 ms 248 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 20348 KB Output is correct
2 Correct 101 ms 20216 KB Output is correct
3 Correct 107 ms 20344 KB Output is correct
4 Correct 159 ms 21624 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 1016 KB Output is correct
2 Correct 904 ms 1016 KB Output is correct
3 Correct 942 ms 1016 KB Output is correct
4 Correct 948 ms 888 KB Output is correct
5 Correct 912 ms 888 KB Output is correct
6 Correct 110 ms 20344 KB Output is correct
7 Correct 101 ms 20216 KB Output is correct
8 Correct 105 ms 20344 KB Output is correct
9 Correct 160 ms 21752 KB Output is correct
10 Correct 39 ms 16376 KB Output is correct
11 Correct 40 ms 16376 KB Output is correct
12 Correct 127 ms 19064 KB Output is correct
13 Correct 37 ms 16376 KB Output is correct
14 Correct 38 ms 16376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 6 ms 504 KB Output is correct
19 Correct 5 ms 504 KB Output is correct
20 Correct 5 ms 504 KB Output is correct
21 Correct 5 ms 504 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 5 ms 504 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 94 ms 2808 KB Output is correct
26 Correct 5 ms 504 KB Output is correct
27 Correct 4596 ms 1048 KB Output is correct
28 Execution timed out 20010 ms 24168 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 1016 KB Output is correct
2 Correct 909 ms 976 KB Output is correct
3 Correct 937 ms 1016 KB Output is correct
4 Correct 942 ms 1016 KB Output is correct
5 Correct 914 ms 1016 KB Output is correct
6 Correct 111 ms 20472 KB Output is correct
7 Correct 106 ms 20344 KB Output is correct
8 Correct 108 ms 20344 KB Output is correct
9 Correct 159 ms 21780 KB Output is correct
10 Correct 39 ms 16376 KB Output is correct
11 Correct 40 ms 16376 KB Output is correct
12 Correct 128 ms 19192 KB Output is correct
13 Correct 38 ms 16376 KB Output is correct
14 Correct 40 ms 16376 KB Output is correct
15 Correct 9597 ms 27856 KB Output is correct
16 Execution timed out 20041 ms 28148 KB Time limit exceeded
17 Halted 0 ms 0 KB -