oj.uz

Submission #204003

# Submission time Handle Problem Language Result Execution time Memory
204003 2020-02-23T14:58:24 Z CaroLinda Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 30260 KB 
#include "wombats.h"
#include <bits/stdc++.h>

#define debug printf
#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 resp[MAXM][MAXM] ;
int h[MAXN][MAXM] ;
int v[MAXN][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] ;

	}

}

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


	calc(0,N-1) ;

}

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

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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16248 KB Output is correct
2 Correct 45 ms 16248 KB Output is correct
3 Correct 125 ms 17912 KB Output is correct
4 Correct 41 ms 16248 KB Output is correct
5 Correct 41 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 376 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 96 ms 2808 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 927 ms 892 KB Output is correct
2 Correct 910 ms 1016 KB Output is correct
3 Correct 929 ms 1056 KB Output is correct
4 Correct 931 ms 888 KB Output is correct
5 Correct 910 ms 888 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 380 KB Output is correct
9 Correct 4593 ms 1016 KB Output is correct
10 Correct 5 ms 376 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 20216 KB Output is correct
2 Correct 109 ms 20216 KB Output is correct
3 Correct 116 ms 20216 KB Output is correct
4 Correct 157 ms 21624 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 868 KB Output is correct
2 Correct 899 ms 1016 KB Output is correct
3 Correct 932 ms 1016 KB Output is correct
4 Correct 927 ms 1016 KB Output is correct
5 Correct 916 ms 1016 KB Output is correct
6 Correct 114 ms 20344 KB Output is correct
7 Correct 114 ms 20220 KB Output is correct
8 Correct 109 ms 20216 KB Output is correct
9 Correct 155 ms 21624 KB Output is correct
10 Correct 42 ms 16376 KB Output is correct
11 Correct 41 ms 16368 KB Output is correct
12 Correct 126 ms 19064 KB Output is correct
13 Correct 40 ms 16248 KB Output is correct
14 Correct 43 ms 16376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 6 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 448 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 504 KB Output is correct
23 Correct 6 ms 504 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 94 ms 2816 KB Output is correct
26 Correct 5 ms 504 KB Output is correct
27 Correct 4610 ms 956 KB Output is correct
28 Execution timed out 20074 ms 23928 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 892 KB Output is correct
2 Correct 925 ms 888 KB Output is correct
3 Correct 941 ms 1084 KB Output is correct
4 Correct 934 ms 1020 KB Output is correct
5 Correct 912 ms 960 KB Output is correct
6 Correct 115 ms 20216 KB Output is correct
7 Correct 114 ms 20216 KB Output is correct
8 Correct 111 ms 20472 KB Output is correct
9 Correct 168 ms 21624 KB Output is correct
10 Correct 40 ms 16248 KB Output is correct
11 Correct 41 ms 16248 KB Output is correct
12 Correct 130 ms 19192 KB Output is correct
13 Correct 41 ms 16248 KB Output is correct
14 Correct 41 ms 16376 KB Output is correct
15 Correct 9512 ms 30260 KB Output is correct
16 Execution timed out 20034 ms 28396 KB Time limit exceeded
17 Halted 0 ms 0 KB -