oj.uz

답안 #204002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204002 2020-02-23T14:46:58 Z CaroLinda 웜뱃 (IOI13_wombats) C++14
9 / 100
 937 ms 20216 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] = resp[j][ curr_c ] = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 16376 KB Output is correct
2 Correct 41 ms 16248 KB Output is correct
3 Correct 129 ms 19080 KB Output is correct
4 Correct 40 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
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 368 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Incorrect 5 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 937 ms 1016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 109 ms 20216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 932 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 929 ms 888 KB Output isn't correct
2 Halted 0 ms 0 KB -