fork download
copy 
  1. /******************************************
  2. *    AUTHOR:         BHUVNESH JAIN        *
  3. *    INSTITUITION:   BITS PILANI, PILANI  *
  4. ******************************************/
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. typedef long long LL;
  9. typedef long double LD;
  10. typedef pair<int,int> pii;
  11. typedef pair<int, int> pll;
  12.  
  13. #define fi			first
  14. #define sec 		second
  15.  
  16. const int MAX = 1e3 + 3;
  17.  
  18. int n, m, q;
  19. int a[MAX][MAX];
  20. int du[4] = {1, 1, -1, -1};
  21. int dv[4] = {1, -1, 1, -1};
  22. int dx[MAX], dy[MAX];
  23. map<int, int> dp[MAX][MAX];
  24.  
  25. int solve(int x, int y, int mask) {
  26. 	// cerr << x << " " << y << " " << mask << "\n";
  27. 	if (mask == (1<<q)-1) {
  28. 		return a[x][y];
  29. 	}
  30. 	if (dp[x][y].find(mask) != dp[x][y].end()) {
  31. 		return dp[x][y][mask];
  32. 	}
  33. 	int res = 0, val;
  34. 	for(int i = 0; i < q; ++i) {
  35. 		if (mask&(1<<i)) {
  36. 			//
  37. 		}
  38. 		else {
  39. 			for(int j = 0; j < 4; ++j) {
  40. 				int _x = x + dx[i] * du[j];
  41. 				int _y = y + dy[i] * dv[j];
  42. 				if (_x >= 0 && _x < n && _y >= 0 && _y < m) {
  43. 					val = solve(_x, _y, mask | (1<<i));
  44. 					res = max(val, res);
  45. 				}
  46. 			}
  47. 		}
  48. 	}
  49. 	return (dp[x][y][mask] = a[x][y] + res);
  50. }
  51.  
  52. int main() {
  53. 	#ifndef ONLINE_JUDGE
  54. 		freopen("inp2.txt", "r", stdin);
  55. 	#endif
  56. 	int t;
  57. 	scanf("%d", &t);
  58. 	while(t--) {
  59. 		scanf("%d %d %d", &n, &m, &q);
  60. 		int sx, sy;
  61. 		scanf("%d %d", &sx, &sy);
  62. 		for(int i = 0; i < q; ++i) {
  63. 			scanf("%d", &dx[i]);
  64. 		}
  65. 		for(int i = 0; i < q; ++i) {
  66. 			scanf("%d", &dy[i]);
  67. 		}
  68. 		for(int i = 0; i < n; ++i) {
  69. 			for(int j = 0; j < m; ++j) {
  70. 				scanf("%d", &a[i][j]);
  71. 				dp[i][j].clear();
  72. 			}
  73. 		}
  74. 		int ans = solve(sx, sy, 0);
  75. 		printf("%d\n", ans);
  76. 	}
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 67136KB
comments (?)
stdin
copy 
3
5 5 2
2 2
1 2
2 1
10 11 62 14 15
57 23 34 75 21
17 12 14 11 53
84 61 24 85 22
43 89 14 15 43
3 3 2
0 0
1 1
1 1
9 8 7
5 6 4
1 3 2
2 2 1
1 1
2
2
5 6
8 3
stdout
copy 
188
24
3
https://ideone.com/k6PWH8
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!