fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <cstring>
  6.  
  7. using namespace std ; 
  8.  
  9. #define vi vector<int>
  10. #define vvi vector< vi > 
  11. #define vs vector<string>
  12. #define vc vector<char>
  13. #define vvc vector< vc >  
  14.  
  15. vvc paths ; 
  16. string path ; 
  17. vvi board ; 
  18. int go( int row , int col , int k ) ; 
  19. void find_path(int row , int col ) ; 
  20. int dp[ 110 ][ 110 ][ 15 ];
  21.  
  22. int K ; 
  23. int N , M ; 
  24. int main() {
  25.  
  26. 	int n , m , k ; 
  27.  
  28. 	cin >> n >> m >> k ; 
  29.  
  30. 	N = n ; 
  31. 	M = m ; 
  32.  
  33. 	board = vvi ( n , vi ( m , 0 ) ) ;
  34.  
  35.  
  36. 	string tmp  ;
  37.  
  38. 	for ( int i = 0 ; i < n ; i ++ ) {
  39.  
  40. 		cin >> tmp ;
  41.  
  42. 		for ( int j = 0 ; j < tmp.size() ; j ++ ) {
  43. 			board[ i ][ j ] = tmp[ j ] - '0' ;
  44. 		}
  45. 	} 
  46.  
  47. 	int mx = -1 ; 
  48. 	K = k + 1 ;
  49. 	int get_col = 0 ; 
  50.  
  51. 	for ( int i = 0 ; i < m ; i ++ ) {
  52. 		memset( dp , -1 , sizeof( dp ) ) ;
  53.  
  54. 		paths = vvc ( n , vc ( m ) ) ;
  55.  
  56. 		int val = go( n - 1 , i , 0 ) ;
  57.  
  58. 		if ( val > mx ) {
  59. 			path.clear() ; 
  60. 			mx = val ;
  61. 			get_col = i + 1 ;  
  62. 			find_path( n - 1 , i ) ;
  63. 		} 
  64. 	}
  65.  
  66. 	if ( mx == -1 ) cout<<-1<<endl;
  67. 	else {
  68. 		cout<<mx<<endl ;
  69. 		cout<<get_col<<endl ;
  70. 		cout<< path << endl ;
  71. 	}
  72.  
  73. 	return 0 ; 
  74. }
  75.  
  76. void find_path(int row , int col ) {
  77. 	if ( row == 0 ) return ; 
  78.  
  79. 	if( paths[ row ][ col ] == 'L' ) {
  80. 		path += 'L';
  81. 		find_path( row - 1 , col - 1 ) ; 
  82. 	}
  83.  
  84. 	else {
  85. 		path += 'R';
  86. 		find_path( row - 1 , col + 1 ) ;
  87. 	}
  88. }
  89.  
  90. int go( int row , int col , int k ) {
  91.  
  92. 	if ( row < 0 || row >= N || col < 0 || col >= M ) return -2 ; 
  93.  
  94. 	if ( dp[ row ][ col ][ k ] != -1 ) return dp[ row ] [ col ] [ k ] ;
  95.  
  96. 	if ( row == 0 ) {
  97. 		if ( ( ( k + board[ row ][ col ] ) % K ) == 0 )  {
  98. 			dp[ row ][ col ][ k ] = board[ row ][ col ] ; 
  99. 			return dp[ row ][ col ][ k ] ; 
  100. 		}
  101.  
  102. 		dp[ row ][ col ][ k ] = -2 ; 
  103. 		return dp[ row ][ col ][ k ] ; 
  104. 	} 
  105.  
  106. 	//int v = board[ row-1 ][ col ] ;
  107.  
  108. 	int L = go ( row - 1 , col - 1 , ( ( k + board[ row ][ col ]  ) % K ) ) ;
  109. 	int R = go ( row - 1 , col + 1 , ( ( k + board[ row ][ col ]  ) % K ) ) ; 
  110.  
  111. 	if ( L > R ) {
  112. 		paths[ row ][ col ] = 'L';
  113. 	}
  114.  
  115. 	else paths[ row ][ col ] = 'R' ; 
  116.  
  117. 	if ( ( int ) max( L , R ) != -2 )  {
  118. 		dp[ row ][ col ][ k ] = max( L , R ) + board[ row ][ col ]; 
  119. 	}
  120.  
  121. 	else dp[ row ] [ col ] [ k ] = -2 ;
  122.  
  123. 	return dp[ row ][ col ][ k ] ;
  124. }
  125.  
Memory limit exceeded #stdin compilation error #stdout 0s 4464KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:42: warning: comparison between signed and unsigned integer expressions
stdout
copy 
Standard output is empty
https://ideone.com/be1hs
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!